Codeforces 173 D. Deputies

問題

n頂点m辺からなる無向二部グラフが与えられる。
このグラフの頂点をちょうどk色で、それぞれの色が3回ずつ現れるように彩色したい。

そのような彩色は可能であるか、不可能ならNOを、
可能ならYESおよび、解を具体的に一つ出力せよ。

制約条件

n, m≦10^5

方針

まずnが3の倍数であることが必要条件。
二部グラフなので、適当にDFSして、頂点を二つの集合U, Vに分ける。

U	が3の倍数ならば、三つずつ取って色を塗ればいいので終了。
U	= 3x + 1,	V	= 3y + 2としてよい。

このとき、Uから一つ頂点uを選び、uに隣接していないVの頂点v, v'を二つ選ぶことができたら、|U|が3の倍数の場合に帰着できるので終了。

Vの側から二つ頂点v1, v2を選び、Uの側からv1につながっていない頂点u1, u1'および、
v2につながっていない頂点u2, u2'をとる。

これが取れないとき、明らかに条件を満たす彩色はない。
取れるとき、実はu1, u1', u2, u2'は全て互いに異なる。
なぜなら、それらのうちの二つがもし等しいとすると、「Uから一つ頂点uを選び、uに隣接していないVの頂点v, v'を二つ選ぶことができなかった」という場合分けに反するから。

ソースコード

int n, m;
vector<vi> e;
int na, v[100000], ans[100000];
int st1[100000], sz1, st2[100000], sz2;

void rec(int c, int cl){
	v[c] = 1;
	if(cl == 1) st1[sz1++] = c;
	else st2[sz2++] = c;
	rep(i, e[c].size()) if(!v[e[c][i]])
		rec(e[c][i], 3 - cl);
}
bool func(int *s, int s_, int *t, int t_, int cnt){
	int res[2], sz = 0;
	rep(i, s_) if((int)e[s[i]].size() <= t_ - 2){
		res[sz++] = s[i];
		if(sz == cnt) break;
	}
	if(sz < cnt) return 0;
	rep(i, sz){
		ans[res[i]] = na++;
		cnt = 0;
		rep(j, t_) if(!binary_search(all(e[res[i]]), t[j])){
			ans[t[j]] = na++;
			if(++cnt == 2) break;
		}
	}
	return 1;
}
void run()
{
	memset(ans, -1, sizeof(ans));
	cin >> n >> m;
	e.resize(n);
	rep(i, m){
		int a, b;
		cin >> a >> b;
		e[--a].pb(--b);
		e[b].pb(a);
	}
	rep(i, n) sort(all(e[i]));
	rep(i, n) if(!v[i]) rec(i, 1);
	if(n % 3){
		cout << "NO" << endl;
		return;
	}
	if(sz1 % 3){
		int *s = st1, *t = st2, s_ = sz1, t_ = sz2;
		if(sz1 % 3 == 2) swap(s, t), swap(s_, t_);
		if(!func(s, s_, t, t_, 1) && !func(t, t_, s, s_, 2)){
			cout << "NO" << endl;
			return;
		}
	}
	rep(i, sz1) if(ans[st1[i]] < 0) ans[st1[i]] = na++;
	rep(i, sz2) if(ans[st2[i]] < 0) ans[st2[i]] = na++;
	cout << "YES" << endl;
	rep(i, n) cout << ans[i]/3 + 1 << (i == n-1 ? "\n" : " ");
}