Codeforces #167 Div1. C. Dima and Horses

さてC。
本番ではDFSでガリガリ書いたが、Pretest通過まで行かず…。
なのでEditorialを見て回答。
http://codeforces.com/contest/273/problem/C

問題

N匹の馬がいる。各馬は、最大３匹まで仲の悪い馬がいる。
馬全体を２つのグループに分けたとき、各馬は同一グループ内に２匹以上の仲が悪い馬がいないようにしたい。
そのような馬の分類を答える。

回答

Editorialを見て回答。
とりあえず全部の馬を同じグループに入れておき、各馬をチェック対象にする。

各馬をチェックしておき、もし同じグループに仲の悪い馬が２匹以上いるなら、自分を反対のグループにする。
また、その際仲の悪い馬を再度チェック対象にする。

このように実質的にDFSをすると最終的に題意を満たす分類になる。

なお、問題文では「そのような分類ができない場合は-1と答えよ」とあるがそのようなことはない。
もし、ある５匹の馬が互いに仲が悪くて完全グラフを作っている場合、それらを２匹－３匹に分けると３匹がわで破綻してしまう。
しかし今回の問題は各馬が仲が悪い馬は最大３匹なので、５匹の完全グラフはできない。

int N,M;
vector<int> E[300001];
int G[300001];
vector<int> C;

void solve() {
	int f,r,i,j,k,l,x,y;
	
	ZERO(G);
	GET2(&N,&M);
	FOR(i,M) {
		x=GETi()-1;
		y=GETi()-1;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	FOR(i,N) C.push_back(i);
	
	FOR(i,C.size()) {
		int ene=0;
		int cur=C[i];
		FOR(j,E[cur].size()) if(G[cur]==G[E[cur][j]]) ene++;
		if(ene>1) {
			G[cur]^=1;
			FOR(j,E[cur].size()) C.push_back(E[cur][j]);
		}
	}
	
	FOR(i,N) _P("%d",G[i]);
	_P("\n");
	
	return;
}

まとめ

なんでこういうGreedyなDFSでうまく行くのか実はよくわかってない。
うーん、そりゃ本番でさらっと回答が出せないよなぁ。