AtCoder Beginner Contest 177 D – Friends を解いた記録
問題の概要
\(1\)から\(N\)までの番号がついた\(N\)人の人がいる．
「人\(A_i\)と人\(B_i\)は友達である」という情報が\(M\)個与えられる．ただし同じ情報が2回以上与えられる可能性がある．
\(X\)と\(Y\)が友達，かつ\(Y\)と\(Z\)が友達であるとき，\(X\)と\(Z\)は友達である．また，すべての友達関係は与えられた情報から導ける．
\(N\)人をいくつかのグループに分ける．このとき，どの人についても「同じグループの中に友達がいない」状態にしたい．これを達成するために必要なグループ数の最小値を求め，出力せよ．
制約
- \(2 \leq N \leq 2 \times 10^5\)
- \(0 \leq M \leq 2 \times 10^5\)
- \(1 \leq A_i, B_i \leq N\)
- \(A_i \neq B_i\)
解法
問題の条件より，ある人\(X\)を起点として友達関係をたどっていったとき，たどり着ける人は全て人\(X\)の友達であることがわかります．
例えば4人の人\(A, B, C, D\)がいて人\((A, B), (B, C), (C, D)\)の組が友達であるとしましょう．このとき人\(A\)を起点として友達関係をたどっていくと，
人\(B\)は人\(A\)の友達です．人\(C\)は人\(B\)の友達なので，人\(C\)も人\(A\)の友達です．また人\(D\)は人\(C\)の友達なので，人\(D\)も人\(A\)の友達です．
このようにして人\(A\)から人\(B, C, D\)にたどり着けますので，人\(A\)から見ると人\(B, C, D\)は全員が友達です．
同様にして，人\(B, C, D\)から見てもすべての人が友達です．
ここで，友達関係を集合として捉えることにしましょう．友達関係にある人同士を同じ集合に入れ，友達関係にない人を別々の集合に入れることにします．すると，上記の例では4人全員が1つの集合に入ります．
また，問題のサンプル1の場合は人\(1, 2, 5\)が友達同士であり，
人\(3, 4\)も友達同士です．しかし人\(1, 2, 5\)と人\(3, 4\)は友達関係ではありません．よってこの場合の友達関係は，\({1, 2, 5}, {3, 4}\)という2つの集合として捉えられます．
ここで問題に戻ります．「同じグループの中に友達がいない」状態を達成するためには，上記のような集合（公式解説で「友達集合」と呼ばれている集合）を考えたとき同一の集合に属する人は別々のグループに振り分ける必要があります．
よって，人数が最も多い友達集合の人数が\(K\)人であるとすると，\(K\)グループは最低でも必要となります（\(K\)グループ未満だと同一の友達集合から2人以上振り分けられるグループができてしまう）．
また，\(K\)グループあれば同一の友達集合に属する人を必ず別々のグループに振り分けられます．よって答えは\(K\)です．
答えを求めるためには，次の操作が必要となります．
- 友達関係の情報を読み取り，そこから友達集合をつくる（友達関係の情報を読み取り，友達集合を適切にまとめる）
- 各友達集合に属する人数を求める
上記の操作は，Union-Findと呼ばれるデータ構造を使うと上手くできます．
実装例
例えばサンプル1の場合，次のような処理を行います．
- はじめ，友達集合は\({1}, {2}, {3}, {4}, {5} \)（各人が別々の友達集合に属している）とする．
- \((1, 2)\)が友達であるため，集合\({1}, {2}\)をまとめる．まとめたあとの状態は\({1, 2}, {3}, {4}, {5} \)である．
- \((3, 4)\)が友達であるため，集合\({3}, {4}\)をまとめる．まとめたあとの状態は\({1, 2}, {3, 4}, {5} \)である．
- \((5, 1)\)が友達であるため，集合\({5}, {1, 2}\)をまとめる．まとめたあとの状態は\({1, 2, 5}, {3, 4} \)である．
- 2つの友達集合に属している人数を求める．3人と2人なので，最大値は3である（これが答え）．
集合をまとめる操作は，上記のコードのunite関数で行います．
各友達集合に属する人数を求める部分ですが，上記のコードでは各要素（人）について根の番号（人）を求め，各人について自身を根とする人数を数えることで対応しました．
root関数を呼べば経路圧縮により全ての（根でない）要素は根に直接ぶら下がる格好となるため，ある要素を根とする人数がそのまま当該要素が属する友達集合の人数となります．
感想
Union-Findはライブラリ整備によりコピペするだけで実装できましたが，人数を数える部分の実装に手こずったのでACするまでには多少の時間を要しました．
全人類がDとEを高速でACしていたので，5完したのにパフォーマンスは1100程度しか出ませんでした．