cf div1 694-Dを解いた.
問題
頂点
辺の無向グラフが与えられる.最初、全ての頂点が白で、次の条件を満たすようにいくつかの頂点を黒く塗ることを考える.
1. 両端が黒い辺が存在しない.
2. 全ての頂点の組について、片端が黒い辺のみを通って移動できる.
このような塗り方が存在するか判定し、存在するならば塗り方を構築せよ.
解法
グラフが連結でなければこのような塗り方は存在しない.
頂点からDFSを行い、その行きがけ順に貪欲に塗っていく.
隣接する頂点に一つでも黒い頂点があれば白、そうでなければ黒で塗れば必ず条件を満たす.
考察
連結なら可能そう
とりあえず全域木を取り、頂点を根としたときの深さの偶奇をもとに色を塗っていくことを考えると、両端が苦をの辺が存在してしまっても後からどうにでも調節できてしまうことがわかる.
