Codeforces #509 Div2 E. Tree Reconstruction

いつもの2500pt/3000ptよりは少し簡単か。
http://codeforces.com/contest/1041/problem/E

問題

N頂点の木を成すグラフがあったとする。
各頂点には1～Nのラベルが振られている。
(N-1)本の辺をそれぞれ切断したとき、両方の連結成分中のラベルの最大値が与えられる。

与えられた情報を満たす木が存在するか。
存在するなら一例を示せ。

解法

まず。ラベルNはどう切断してもN側の連結成分の最大値はNになる。
よって、両方のうち片方は必ずNでなければならない。
入力中、(A,N)という対がm個あったとする。
この場合、AとNの間に(m-1)個A未満の値を挟めばよい。
なお、この時挟む値Bは(B,N)が入力に存在しないものでなければならない。
そのようなものが(m-1)個準備できないなら解なしとなる。

int N;
int cnt[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		cnt[x]++;
		cnt[y]++;
	}
	
	if(cnt[N]!=N-1) return _P("NO\n");
	if(cnt[N-1]==0) return _P("NO\n");
	
	vector<pair<int,int>> V;
	vector<int> cand;
	for(i=1;i<=N-1;i++) {
		if(cnt[i]==0) cand.push_back(i);
		else {
			if(cand.size()<cnt[i]-1) return _P("NO\n");
			int pre=N;
			FOR(j,cnt[i]-1) {
				V.push_back({cand.back(),pre});
				pre=cand.back();
				cand.pop_back();
			}
			V.push_back({i,pre});
		}
	}
	cout<<"YES"<<endl;
	FORR(v,V) cout<<v.first<<" "<<v.second<<endl;
	
}

まとめ

考察メインで実装は軽めの問題。