Codeforces Global Round 20 : F2. Checker for Array Shuffling

たまにこのタイプの問題出るね。
https://codeforces.com/contest/1672/problem/F2

問題

Codeforces Global Round 20 : F1. Array Shuffling - kmjp's blog
この問題に対する回答が与えられるので、正誤判定をせよ。

解法

頂点A[i]→頂点B[i]に有向辺を張ったグラフを考える。
この時、閉路の数が最小であれば条件を満たすことになる。

A中の最頻値をxとすると、全閉路にxが含まれていればよいことになる(それ以上閉路の数を減らせないため)。
よって、逆にxを含まない閉路が無いか判定すればよい。

int T,N,A[202020],B[202020];
vector<int> E[202020];
int vis[202020];
int ret;

void dfs(int cur) {
	if(vis[cur]==2) {
		ret=1;
		return;
	}
	if(vis[cur]==1) return;
	vis[cur]=2;
	FORR(e,E[cur]) dfs(e);
	vis[cur]=1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		FOR(i,N+1) vis[i]=0,E[i].clear();
		int ma=0;
		FOR(i,N) {
			cin>>A[i];
		}
		FOR(i,N) {
			cin>>B[i];
			E[A[i]].push_back(B[i]);
			if(E[A[i]].size()>E[ma].size()) ma=A[i];
		}
		
		vis[ma]=1;
		ret=0;
		FOR(i,N+1) if(vis[i]==0) dfs(i);
		if(ret) {
			cout<<"WA"<<endl;
		}
		else {
			cout<<"AC"<<endl;
		}
	}
}

まとめ

本番F1で手間取りすぎてる時点でダメだな…。