ABC 401-500/ABC404C - Cycle Graph? - 競技プログラミング用 知識集積所

---

問題

ABC404C

必要知識

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

• 必要十分条件（未作成）
• 隣接リスト（未作成）
• UnionFind木（未作成）

考え方

サイクルグラフであることの必要十分条件を考える。

まず、サイクルグラフであれば、全ての頂点から2本の辺が出ている。
しかし、全ての頂点から2本の辺が出ていればサイクルグラフかといえばそうではない。
なぜなら、1-2-3-1でサイクル、4-5-6-4でサイクル、のように複数のサイクルに分かれてしまっている場合があるため。

そこで、きちんと1つのサイクルになっていることを保証するため、UnionFind木を用いて連結成分が1つであることを確認する。

解答例

解答例

注意点

別解

幅優先探索（未作成）で対応する。

まず、1つ目の辺を切断する。
1つ目の辺の片側からを支点としてBFSを行い、逆の片側までの最短距離がn-1であるかどうかを判定することで解ける。
m=0の場合の特別対応が必要なことに注意。
解答例（未作成）