2020-11-20

Codeforces Round #684 (Div. 1) B. Graph Subset Problem (R2600)

Codeforces グラフ NP困難(特殊構造なので解ける) クリーク後退解析 queue 葉から考える制約条件:グラフの次数列 Yes/No判定問題復元どれか1つ求める定数倍高速化部分グラフ列挙問題見積り大事 O(√N)まで考えれば十分 CodeforcesDIV1-B CodeforcesR2600

TLE が厳しくて話題になってた

問題へのリンク

問題概要

頂点数 $N$ 、辺数 $M$ の単純無向グラフ [tex G] が与えられる。また、正の整数 $K$ が与えられる。

以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。

type 1： $G$ の部分グラフであって、それに含まれるどの頂点についても、次数が $K$ 以上である
type 2： $G$ の部分グラフであって、サイズ $K$ のクリークである (頂点数が $K$ でどの頂点も次数が $K-1$ であるもの)

制約

$1 \le N, M, K \le 10^{5}$

考えたこと

まず type 1 に関しては、「サイクル検出をするのに queue を使って葉がある限り除去していく」と、同じ方法が使える！　つまり、

次数 $K-1$ 以下の頂点がある限りそれを削除していく
削除することで新たに次数 $K-1$ の頂点が生じる場合も、改めてそれを削除していく

という処理を行なっていく。もし何も残らなければ、type 1 の条件を満たすものは存在しない。残ったならば、それは type1 の条件を満たすものとなる。

サイズ $K$ のクリーク

サイズ $K$ のクリークとは、どの頂点の次数も $K-1$ であるような頂点数 $K$ の部分グラフである。

よって、先ほどの手続きを修正して、次のように探索できる。

次数 $K-2$ 以下の頂点がある限りそれを削除していく (その過程で新たに次数 $K-2$ 以下の頂点が生じる場合も、改めてそれを削除していく)
それによって次数 $K-1$ 以上の頂点集合が残る
次数がちょうどであるような頂点については、それがクリークをなしうるかどうかを次のように判定できる
- 頂点 $v$ とそれに隣接する頂点からなるサイズ $K$ の頂点集合がクリークをなすかどうかを判定する
- クリークをなさないならば、頂点 $v$ は type 1, type 2 のいずれのメンバーにもなり得ないので削除してよい
この手続きによってクリークが発見されずに、次数 $K-1$ の頂点が消滅したとしても、残る頂点はすべて次数が $K$ 以上となるので、type 1 を満たす

以上の手続きの計算量を評価する

次数の頂点が発掘されてクリークかどうかを確かめる回数はとなる
- 1 回削除されるごとに辺数が $K$ 減少するため
1 回のクリーク判定は $O(K^{2} \log N)$ 程度の計算量を要する

$K \gt \sqrt N$ である場合はクリークが存在しえないことに注意すると、計算量は $O(M\sqrt{N}\log N)$ 程度といえる。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

/*
    K-1 未満はガンガン削除していく
    K-1 が生えたら、それと K-1 個の頂点でできる K 頂点部分グラフを判定
        ダメならその K-1 頂点も不要なので削除

    もしクリークがあれば、この過程で見つかる
    クリークがなけれ操作終了時には、どの頂点も次数 K 以上の部分グラフが残るはず
*/

using Graph = vector<vector<int>>;
bool solve(int N, int M, int K, Graph &G) {
    if ((long long)(K) * (K-1) / 2 > M) return false;
    for (int v = 0; v < N; ++v) sort(G[v].begin(), G[v].end());
    vector<int> deg(N, 0);
    vector<bool> removed(N, 0);

    // 1: K, 2: クリーク
    auto print = [&](int type, const vector<int> &res) -> void {
        if (type == 1) printf("%d %d\n", type, (int)res.size());
        else printf("%d\n", type);
        for (int i = 0; i < res.size(); ++i) {
            if (i) printf(" ");
            printf("%d", res[i]+1);
        }
        printf("\n");
    };
    auto isclique = [&](int v) -> bool {
        vector<int> res({v});
        for (auto u : G[v]) if (!removed[u]) res.push_back(u);
        if (res.size() != K) return false;
        for (int i = 0; i < res.size(); ++i) {
            for (int j = i+1; j < res.size(); ++j) {
                int s = res[i], t = res[j];
                int it = lower_bound(G[s].begin(), G[s].end(), t) - G[s].begin();
                if (it == G[s].size() || G[s][it] != t) return false;
            }
        }
        print(2, res);
        return true;
    };

    queue<int> que;
    vector<bool> seen(N, false);
    for (int v = 0; v < N; ++v) {
        deg[v] = (int)G[v].size();
        if (deg[v] <= K-1) que.push(v), seen[v] = true;
    }
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        if (deg[v] == K-1 && isclique(v)) return true;
        for (auto u : G[v]) {
            --deg[u];
            if (!seen[u] && deg[u] <= K-1) que.push(u), seen[u] = true;
        }
        removed[v] = true;
    }
    
    vector<int> res;
    for (int v = 0; v < N; ++v) if (!removed[v]) res.push_back(v);
    if (!res.empty()) {
        print(1, res);
        return true;
    }
    return false;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int N, M, K;
        scanf("%d %d %d", &N, &M, &K);
        Graph G(N);
        for (int i = 0; i < M; ++i) {
            int u, v;
            scanf("%d %d", &u, &v);
            --u, --v;
            G[u].push_back(v), G[v].push_back(u);
        }
        if (!solve(N, M, K, G)) printf("%d\n", -1);
    }
}