- 考えたこと
- 人を頂点として「共通言語がある」を辺とした時に、グラフが連結であるかどうか判定せよという問題
- 人が10^5いるので、人のペアに対して辺の有無を判定すると10^10になってしまうから素朴にはできない
- Kiの総数が上限10万なのが重要そう
- 素朴にはNMで10^10になるところに強い制約が追加されてるから
- これに対して線形オーダーの処理をするのはOKだよ、ということかと
- 「言語→その言語を話す人の集合」を作る。線形オーダー
- この集合の中の人は連結
- UnionFindに入れる、O(n log n)
- 最後に全員のrootが同じかどうか調べれば良い、O(n log n)
- 公式解説
- 原理としては同じだが「言語も頂点に入れて二部グラフと解釈」という整理
- N+M頂点のグラフに増えるが、辺の本数が10^5に抑えられてるのでUnionFindで間に合う