【ABC】 177 D - Friends

最近Cまでしか解けずレートが全然上がりません...。
今回のD問題も方針自体は分かったのですが、友達の数が最も多い集団を探す関数の計算量が抑えきれずTLEしてしまいました。
解説動画でも紹介されていたUnion Findを用いた実装をしてみました。
こちらを参考にしてpythonで実装しました。

atcoder.jp

提出したコードは以下のgithubリポジトリにあります。
rank[x]にノードxを根とした時にそれより下の階層に繋がっているノードの数が格納されています。
uniteするときも木構造同士のrankを調べて加算しています。
最後に全てのノードを調べて最大のrank+1を返しています。

github.com

結果

atcoder.jp