競技プログラミング用 知識集積所
ABC404C - Cycle Graph?
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
サイクルグラフであることの必要十分条件を考える。
まず、サイクルグラフであれば、全ての頂点から2本の辺が出ている。
しかし、全ての頂点から2本の辺が出ていればサイクルグラフかといえばそうではない。
なぜなら、1-2-3-1でサイクル、4-5-6-4でサイクル、のように複数のサイクルに分かれてしまっている場合があるため。
しかし、全ての頂点から2本の辺が出ていればサイクルグラフかといえばそうではない。
なぜなら、1-2-3-1でサイクル、4-5-6-4でサイクル、のように複数のサイクルに分かれてしまっている場合があるため。
そこで、きちんと1つのサイクルになっていることを保証するため、UnionFind木を用いて連結成分が1つであることを確認する。
