Codeforces 167C (273C) Dima and Horses
問題
それぞれの頂点の次数が3以下の無向グラフが与えられる。
このグラフの頂点を0か1の色に塗り分けて、
すべての頂点について、その頂点につながる同じ色の頂点の数を1つ以下にしたい。
そのような塗り方を具体的に一つ求めよ。
不可能な場合は-1を返せ。
制約条件
n, m≦300000
方針
逐次改善を繰り返せば必ず答えが出る。
すなわち、同じ色の頂点が2つ以上つながっている頂点を取って、
その頂点の色を反転させるということを、更新ができなくなるまで繰り返せば、答えが求まる。
更新ができないということは、同じ色の頂点が2つ以上つながっている頂点がないということなので、条件を満たしている。
また、この逐次改善は必ず終了する。
なぜなら、違う色の頂点同士を結ぶ辺の数は、この操作において必ず減少する。
(一回の操作で、違う色を結ぶ辺が2本以上減って、同じ色を結ぶ辺が1本以下増えるため)
辺の数は0以上なので、この操作は必ず終了する。
ソースコード
const int MX = 300000; int n, m; vector<vi> e; vi bad; int cnt[MX], col[MX]; int main(){ cin >> n >> m; e.resize(n); rep(i, m){ int a, b; cin >> a >> b; a--; b--; e[a].pb(b); e[b].pb(a); } rep(i, n){ cnt[i] = e[i].size(); if(cnt[i] > 1) bad.pb(i); } while(bad.size()){ int c = bad.back(); bad.pop_back(); if(cnt[c] < 2) continue; rep(i, e[c].size()){ int to = e[c][i]; if(col[to] == col[c]){ cnt[c]--; cnt[to]--; } else{ cnt[c]++; if(cnt[to]++ == 1) bad.pb(to); } } col[c] ^= 1; } rep(i, n) putchar('0' + col[i]); puts(""); return 0; }