ABC 401-500/ABC411F - Contraction - 競技プログラミング用 知識集積所

---

問題

ABC411F

必要知識

B以下レベルの内容は省略

• UnionFind木（未作成）の頂点管理法

考え方

頂点AとBを合併するなら、頂点Bにつながっている辺を全部頂点Aに繋ぎなおしてやればいい。
そして、発生した自己ループと多重辺を削除した分だけ辺の数を減らしていく。
実はこれを無駄な処理が発生しないように愚直に実装するだけで間に合う。

問題は、頂点管理のところで無駄な処理が発生しやすいこと。
AとBを合併して全部Aに繋ぎなおした場合、以後頂点Bを指定された場合、代わりに頂点Aを指定されたつもりで処理しなければならない。
これが数千段階重なるテストケースを渡されると、「結局どこと思えばいいの？」の処理に数千回の処理が必要になってTLEする。

これはUnionFind木（未作成）を自力実装すると全く同じ問題を抱えるところであり、つまり全く同じ方法で解消できる。
すなわち、「結局どこと思えばいいの？」を探索するたびに、探索途中で通った頂点全てにその情報を残すように更新しておけばよい。

解答例

解答例

注意点

別解

UnionFind木そのものを使う

意外にも、そのものを使っても間に合うらしい。
合体している頂点の数が少ない方が辺の数が多い、というパターンが続くと処理が重そうだが……？
そういうパターンのテストケースを作り忘れたのか、それともそういうパターンでも何かの理由で大して負担は増えないのか。
解答例