yukicoder : No.2998 Rainbow Christmas Tree

なるほど…。
https://yukicoder.me/problems/no/2998

問題

ラベル付きN点に対し、(N-1)通りの有向全域木が与えられる。
K個は頂点1を根とし、(N-1-K)個は頂点Nを根とする。

各全域木から1本ずつ辺を選んで組み合わせ、有向全域木を構築できるか。
できるなら一例を示せ。

解法

K=0またはK=N-1、すなわち根が1個の場合を考える。
S={1}から初めて、各全域木に対し、S内からS外の点に張られた辺を1つ選んで追加していこう。
これで最終的に|S|=N、つまり有向全域木ができる。

Kがそれ以外の場合、まず点vとして、vから頂点1を根とする全域木の辺で頂点Nに到達でき、かつ頂点Nを根とする全域木の辺で頂点1に到達できるものを探そう。
そうすれば、頂点v→頂点1と、頂点v→頂点Nのパスができるので、あとはK=0やK=N-1の時と同じロジックを使えば頂点vを根とする全域木が作れる。

int N,K;
int P[1010][1010];
vector<int> E[1010][1010];
pair<int,int> pat[2][1010];
int ret[1010];
int used[1010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N-1) {
		FOR(j,N) {
			cin>>P[i][j+1];
			if(P[i][j+1]) E[i][P[i][j+1]].push_back(j+1);
		}
	}
	
	set<int> S;
	if(K==0||K==N-1) {
		if(K==0) S.insert(N);
		else S.insert(1);
	}
	else {
		set<int> S1={1},S2={N};
		x=0;
		MINUS(pat);
		FOR(i,N-1) if(x==0) {
			if(i<K) {
				FORR(s,S2) if(P[i][s]&&S2.count(P[i][s])==0) {
					pat[0][P[i][s]]={i,s};
					S2.insert(P[i][s]);
					break;
				}
			}
			else {
				FORR(s,S1) if(P[i][s]&&S1.count(P[i][s])==0) {
					pat[1][P[i][s]]={i,s};
					S1.insert(P[i][s]);
					break;
				}
			}
			FORR(s,S1) if(S2.count(s)) x=s;
		}
		S.insert(x);
		FOR(i,2) {
			y=x;
			int tar=(i==0)?N:1;
			while(y!=tar) {
				j=pat[i][y].second;
				ret[j]=pat[i][y].first+1;
				used[pat[i][y].first]=1;
				y=j;
				S.insert(y);
			}
		}
	}
	FOR(i,N-1) if(used[i]==0) {
		FORR(s,S) FORR(e,E[i][s]) if(S.count(e)==0) {
			ret[e]=i+1;
			S.insert(e);
			goto out;
		}
		out:
		;
	}
	cout<<"Yes"<<endl;
	FOR(i,N) cout<<ret[i+1]<<" ";
	cout<<endl;
}

まとめ

わかってしまえば簡単だけど、それを自力で思いつくのが難しい。