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;
}