きろく

特筆すべき記録のまとめ

AtCoder Grand Contest 035:B - Even Degrees

問題

https://atcoder.jp/contests/agc035/tasks/agc035_b

解法

まず,辺の数が奇数の時は答えは No になる.偶数の時は答えを構成することができる.

簡単な場合として根付き木を考える.このとき各頂点の出次数の偶奇は葉から各辺の向きを決めることで操作することができる.具体的には,頂点 v の出次数の偶奇を変えたい場合は頂点 v の親の頂点に向けて辺の向きを設定すればよく,変えない場合はその逆の向きにすればよい.根の出次数は,ほかの頂点の出次数が全て偶数であり辺の数も偶数であることから,必ず偶数になる.

与えられたグラフは連結なので必ず全域木を構成することができる.この全域木に含まれる辺以外の辺の向きは適当に決めてしまう.そうすることで,全域木においての各頂点の出次数の偶奇が決まる.この決まった偶奇をもとに全域木の葉から順に前述の通りに操作をしていけばよい.O(N + MlogM).

解答

https://atcoder.jp/contests/agc035/submissions/6413394

グラフの簡単な場合として木から考えるという考え方を学んだ.

f:id:babcs2035:20190717145603p:plain