codefestival_2016_final_C

https://gyazo.com/ba263384ca6d2220146d053b4cf027c8

考えたこと

人を頂点として「共通言語がある」を辺とした時に、グラフが連結であるかどうか判定せよという問題

人が10^5いるので、人のペアに対して辺の有無を判定すると10^10になってしまうから素朴にはできない

Kiの総数が上限10万なのが重要そう

素朴にはNMで10^10になるところに強い制約が追加されてるから

これに対して線形オーダーの処理をするのはOKだよ、ということかと

「言語→その言語を話す人の集合」を作る。線形オーダー

この集合の中の人は連結

最後に全員のrootが同じかどうか調べれば良い、O(n log n)

公式解説

原理としては同じだが「言語も頂点に入れて二部グラフと解釈」という整理

N+M頂点のグラフに増えるが、辺の本数が10^5に抑えられてるのでUnionFindで間に合う