Codeforces #902 : Div1 C. Autosynthesis

よくこういう問題思いつくな。
https://codeforces.com/contest/1876/problem/C

問題

整数列Aが与えられる。
Aのいくつかの要素を〇で囲うことを考える。
1要素を複数回囲っても良い。

1回も囲まれていない要素からなる整数列をPとする。
Pの各値に対し、対応するAのindexに〇をつけたとき、元々Aにつけた○と一致するようにしたい。
条件を満たすPが存在するなら1つ求めよ。

解法

A[i]→iと辺を張った、N点N辺の有向グラフを考える。
○で囲った点は黒、そうでない点は白で塗るとする。

このグラフは、親は1つで子は複数あり得る。

• もし子に白い要素があればその点は黒
• もし子がなければ、その点は白

を満たすように、葉から順に白黒を決めていこう。
もし閉路ができる場合、長さが偶数なら白黒交互に塗ればよい。

int N;
int A[202020];
vector<int> E[202020];
int in[202020];
int C[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		E[A[i]].push_back(i);
		in[A[i]]++;
	}
	queue<int> Q;
	FOR(i,N) {
		if(in[i]==0) Q.push(i);
	}
	MINUS(C);
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		if(C[cur]>=0) continue;
		C[cur]=0;
		FORR(e,E[cur]) if(C[e]==0) C[cur]=1;
		in[A[cur]]--;
		if(in[A[cur]]==0||C[cur]==0) Q.push(A[cur]);
	}
	FOR(i,N) if(C[i]==-1) {
		vector<int> V={i};
		while(A[V.back()]!=i) {
			V.push_back(A[V.back()]);
		}
		if(V.size()%2) {
			cout<<"-1"<<endl;
			return;
		}
		FOR(j,V.size()) {
			C[V[j]]=j%2;
		}
	}
	vector<int> cand;
	FOR(i,N) {
		x=0;
		FORR(e,E[i]) if(C[e]==0) x++;
		if(x>0 != C[i]) {
			cout<<"-1"<<endl;
			return;
		}
		if(C[i]==0) cand.push_back(A[i]+1);
	}
	cout<<cand.size()<<endl;
	FORR(e,cand) cout<<e<<" ";
	cout<<endl;
	
	
}

まとめ

コーナーケースとか意外にめんどい。