Codeforces #285 Div1 A. Misha and Forest

CF285に参加。
ABをさっさと解いたところ、CDは解けなかったけど大量にCDが落ちたため結構良い順位に落ち着いた。
http://codeforces.com/contest/504/problem/A

問題

0～(N-1)の番号を持つN個の頂点からなる、森を成すグラフがある。
ここで、各頂点に対し、辺で直接接続された頂点の数と、それら頂点の番号のxorを取った値S[i]が与えられる。

グラフを構成する辺を列挙せよ。

解法

グラフが森を成すということは閉路がない。
そのため、辺があるならば次数１の頂点が必ず存在するはずである。
また、次数１の頂点iに対しては、S[i]は接続された頂点番号を示すはずである。

よって、iとS[i]をつなぐ辺が存在する。
そのような辺を解に追加すると同時に、S[i]番の頂点の次数を1つ減らし、S[S[i]] ^= iでS[S[i]]を更新する。
１個辺を追加するごとにどこかの頂点の次数が１個減るので、連鎖的に次数１の頂点が発生するため順次処理していけば良い。

int N;
int D[1<<17],S[1<<17];
vector<pair<int,int> > V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	queue<int> Q;
	FOR(i,N) {
		cin>>D[i]>>S[i];
		if(D[i]==1) Q.push(i);
	}
	
	while(Q.size()) {
		int k=Q.front();
		Q.pop();
		if(D[k]==0) continue;
		D[k]--;
		x=S[k];
		V.push_back(make_pair(k,x));
		D[x]--;
		S[x]^=k;
		if(D[x]==1) Q.push(x);
	}
	_P("%d\n",V.size());
	FOR(i,V.size()) _P("%d %d\n",V[i].first,V[i].second);
	
}

まとめ

次数１の点のS[i]は接続先を示す、ということに気づけばすぐだね。
Div1Aとしてお手頃な良問だと思う。