AtCoder Beginner Contest 287 C問題 Path Graph?
問題
提出解答
問題の概要
以下の 頂点
辺の単純無向グラフ
は Path グラフか?
制約
は単純グラフ
解法
以下の特徴づけを用いる.
無向グラフ において, 以下は同値である.
は Path グラフである.
は木で, 次数が
以下の頂点が
個である
ここで, が木であることと,
が
頂点のとき,
が
辺の連結グラフであることは同値であるため, 以下を全て満たすかどうかを判定すればよい.
は連結である
- 次数が
の頂点の数が
個である.
これらはそれぞれ次のように判定すればよい.
- 入力の
から直ちに判定できる.
- BFS, DFS, Union-Find を利用することにより, 連結性を判定できる.
に登場する
の個数が頂点
の次数である.
これらを判定することによって, 時間で判定できる.