AGC035B - Even Degrees
出次数は mod 2 で考えてもよい。このとき、辺$${i}$$の向きを flip をすることは、頂点$${A_i, B_i}$$の出次数を flip することと同値になる。
いま、ある相異なる頂点$${u, v}$$が存在して、いずれの出次数も 1 であるとする。与えられるグラフは連結であるから$${u, v}$$を繋ぐ単純パス$${P}$$が少なくとも 1 つ存在する。$${P}$$に含まれる辺の向きをすべて flip することで$${u, v}$$の出次数だけを flip することができる。
各辺を flip した回数はオイラーツアーと累積和を用いて、前計算$${\Theta(N+M)}$$クエリあたり$${\Theta(1)}$$で求めることができる。最終的に$${\Theta(N+M)}$$時間で解くことができた。
この記事が気に入ったらサポートをしてみませんか？