問題概要
$N$ 人の人がいて，「人 $A_i$ と人 $B_i$ が友達である」という情報が $M $ 個与えられる．ここで，友達関係は transitive である（その情報が与えられるとは限らない*1）．
人々をいくつかのグループに分け，任意の人について「同じグループに友人がいない」状態を作りたい．最小でいくつのグループを作る必要があるか？
制約
- $2 \leq N, M \leq 2 \times 10^5$
解法
人を頂点，友達関係を辺としたグラフを考えてみると，友達関係の transitivity から，このグラフはクリークをいくつか集めてきたグラフ（それぞれの連結成分がクリークという意味）になっています．鳩ノ巣原理的に考えると，最大のクリークサイズ未満のグループ数では，友達同士で同じグループに入ってしまいます．一方，最大クリークサイズと同じだけのグループ数があれば，友達同士をバラけさせてグループ分けできます．
ということで，最大クリークサイズが欲しい気になってきますが，今回は一般のグラフではなくかなり制限された形のグラフなので*2，比較的簡単に解くことができます．特別な道具を使わないのであれば，DFS などで連結成分毎に頂点数を数える手法が有効です．素集合データ構造*3があれば，unite 時の操作にちょっと書き足すだけで，グループ毎にサイズを求めることができます．
コード
class DisjointSetForest; bool DisjointSetForest::unite( int x, int y ) { x = find( x ); y = find( y ); if ( x == y ) { return false; } if ( rank[x] < rank[y] ) { parent[x] = y; sizes[y] += sizes[x]; } else { parent[y] = x; sizes[x] += sizes[y]; if ( rank[x] == rank[y] ) { ++rank[x]; } } --groups_; return true; } // DisjointSetForest( N ) // find( x ) // same( x, y ) // unite( x, y ) // groups() // groupSize( x ) int main() { IN( int, N, M ); DisjointSetForest dsf( N ); REP( M ) { IN( int, u, v ); --u, --v; dsf.unite( u, v ); } int res = 0; REP( i, N ) { chmax( res, dsf.groupSize( i ) ); } cout << res << endl; return 0; }
