AIM Tech Round : A. Graph and String

体調悪い中押して出たらミス連発で0完やらかした…。
http://codeforces.com/contest/623/problem/A

問題

N個の頂点があり、それぞれa～cのいずれかのアルファベットのラベルが振られている。
ラベルのアルファベットの距離が1以下の頂点対のみ、もれなく頂点間に辺を張ることを考える。

こうして得られたグラフが与えられる。
グラフの辺に矛盾しないような頂点のラベルの組み合わせが存在すれば１例を答えよ。

解法

全頂点対に辺があれば、全部同じラベルで良い。
そうでない場合、辺が張られてない頂点対(x,y)を1つ求めよう。

頂点xのラベルを'a'、頂点yのラベルを'c'とすると、他の頂点はx,yとの辺の付き方からラベルの内容が一意に定まる。
こうして作ったラベルの割り当てについて、最後にもう一度矛盾がないか検証すればよい。

int N,M;
int G[501][501];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		G[x-1][y-1]=G[y-1][x-1]=1;
	}
	
	int a=-1,c=-1;
	FOR(y,N) FOR(x,y) if(G[x][y]==0) a=x,c=y;
	if(a==-1) {
		cout<<"Yes"<<endl;
		cout<<string(N,'a')<<endl;
		return;
	}
	
	string S=string(N,'-');
	S[a]='a';
	S[c]='c';
	
	FOR(i,N) if(i!=a && i!=c) {
		if(G[i][a]==0 && G[i][c]==0) {
			cout<<"No"<<endl;
			return;
		}
		if(G[i][a]==1 && G[i][c]==0) S[i]='a';
		if(G[i][a]==0 && G[i][c]==1) S[i]='c';
		if(G[i][a]==1 && G[i][c]==1) S[i]='b';
	}
	
	FOR(y,N) FOR(x,y) if(G[x][y]^(abs(S[x]-S[y])<=1)) {
		cout<<"No"<<endl;
		return;
	}
	
	cout<<"Yes"<<endl;
	cout<<S<<endl;
	
}

まとめ

２重ループを書いたところがなぜか１重になっててWAした…。