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

問題のリンク

問題概要

$N$ 頂点 $M$ 辺からなる単純グラフが与えられる。次の条件のいずれかを満たすような部分グラフを1つ求めよ。存在しない場合は-1を出力。

部分グラフ内の全ての頂点が少なくとも $K$ 個以上の隣接する頂点を持つ
サイズ $K$ のクリークである

制約

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

解法

最初に自明なケースを取り除きます。

サイズ $K$ のクリークはグラフ内に $\frac{K(K-1)}{2}$ 本の辺を持つので、

$\frac{K(K-1)}{2} \gt M$ を満たす時、明らかに条件を満たす部分グラフは存在しない。

1番目の条件は簡単に処理可能。

そもそも始めの時点で入次数が $K$ に満たない頂点は条件を満たす部分グラフに含まれることはないので、その頂点及びその頂点から伸びる辺を取り除いていく。

この操作を次数が $K$ 未満の頂点が無くなるまで繰り返し行い、空ではない部分グラフが残ればそれが条件1を満たす部分グラフとなります。

2番目の条件の、大きさ $K$ のクリークの存在判定問題はNP困難な問題として知られています。

ここで1番目の条件が大きく関わってきます。なぜなら、本来の問題では次数が $K$ より大きい頂点についてもクリーク判定をしないといけないのに対し、今回は次数 $K$ より大きい頂点が存在すれば条件1の時点で除かれているため次数 $K-1$ の頂点についてだけ調べれば良いからです。

計算量について、一つの頂点についてクリーク判定をするのに $O(K^{2})$ 、調べる頂点数について1回の判定ごとに $K-1$ 本ずつ辺が取り除けるので $O(\frac{M}{K})$ 程度に抑えられ、始めの考察より、 $K\leqq\sqrt M$ が言えるので全体で $O(M^\frac{3}{2})$ 。ここにクリーク判定時に辺を管理するためstd::set等を用いてlogがついて(TLが1secと厳しいので)定数倍で通ったり通らなかったりします。

コンテスト終了後の感想戦では、探索順シャッフルやstd::unordered_mapを使用するなどの工夫を見かけました。

そんな中、熨斗袋さんが颯爽と計算量のlogを落とす方法を考案していました。

1. 次数 k-1 の頂点のそれぞれについて、隣接点に自分の頂点番号を送る
2. 長さ n の bool 配列 a を用意
全ての頂点 v について
3. a[v の隣接点] ← true
4. 1. で v に送って来た頂点について、a を使って隣接判定
5. a を戻す
— 熨斗袋 (@noshi91) 2020年11月17日

実装

熨斗さんの方法を用いるとTL1secでも余裕を持って通すことができました。

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

void solve(){
    int n,m,k; cin >> n >> m >> k;
    vector<vector<int>> g(n);
    vector<int> deg(n,0); // グラフの次数
    for(int i=0;i<m;i++){
        int x,y; cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
        deg[x]++; deg[y]++;
    }
    vector<bool> done(n,false);
    vector<int> vec; // 次数がK未満の頂点
    vector<vector<int>> adj(n),check(n);
    for(int i=0;i<n;i++){
        if(deg[i]<k)vec.push_back(i);
    }
    while(vec.size()){
        int s=vec.back();
        vec.pop_back();
        done[s]=true;
        if(deg[s]==k-1){
            for(int t:g[s]){
                if(done[t])continue;
                adj[s].push_back(t);
                check[t].push_back(s);
            }
        }
        for(int t:g[s]){
            deg[t]--;
            if(deg[t]==k-1)vec.push_back(t);
        }
    }
    for(int i=0;i<n;i++){
        if(!done[i])vec.push_back(i);
        // vectorを使いまわしてます　分かりづらい
    }
    if(vec.size()){
        printf("1 %d\n",vec.size());
        for(int i=0;i<vec.size();i++){
            printf("%d ",vec[i]+1);
        }
        printf("\n");
        return;
    }
    vector<bool> is_ok(n,true);
    vector<int> flag(n,0);
    for(int i=0;i<n;i++){
        // 熨斗さんの手法 
        // https://twitter.com/noshi91/status/1328752202505093120
        for(int v:g[i]){
            flag[v]=1;
        }
        flag[i]=1;
        for(int v:check[i]){
            for(int u:adj[v]){
                if(!flag[u]){
                    is_ok[v]=false;
                }
            }
        }
        flag[i]=0;
        for(int v:g[i]){
            flag[v]=0;
        }
    }
    for(int i=0;i<n;i++){
        if(adj[i].size()!=k-1)continue;
        if(is_ok[i]){
            printf("2\n");
            printf("%d",i+1);
            for(int v:adj[i]){
                printf(" %d",v+1);
            }
            printf("\n");
            return;
        }
    }
    printf("-1\n");
    return;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int q; cin >> q;
    while(q--){
        solve();
    }
}

かっつのメモ帳

主に競プロ　時々日記

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

問題概要

制約

解法

実装