Codeforces #319 Div1 B. Invariance of Tree

なかなか面白かった。Hackも9個も取れたしね。
http://codeforces.com/contest/576/problem/B

問題

1～Nのpermutation P[i]が与えられる。
以下の条件を満たすN頂点の木が作れるか、作れるなら条件を満たせ。

• 頂点u,v間の辺の有無とP[u],P[v]間の有無は一致する

解法

頂点xに対し、x,P[x],P[P[x]],...と並べていくといずれxに戻る。
ここで、その周期が3以上の場合、これらの間に辺はつなげられない。
なぜなら、xとP[x]の間に辺があると、P[x]とP[P[x]]の間も辺が無ければならず、以後同様に周内の点を結ばなければならず閉路が生じるためである。
周期が1または2ならこの問題は生じない。

• 周期1、すなわちx=P[x]となる頂点xがある場合
  • 他の頂点yをすべてxと連結すればよい。各頂点はxとしか辺をもたないのだから、他の周期性を持つ頂点同士の間にそもそも辺をもたず、上記問題が生じない。
• 周期2、すなわちx=P[P[x]]となる頂点xがある場合
  • まずxとP[x]を結ぼう。
  • 残りの頂点はすべて周期が偶数でなければならない。その場合、周内のy,P[y],P[P[y]],P[P[P[y]]], ... はxとP[x]交互に辺を結べば良い。
• 上記の条件を満たさない場合、すなわち「周期1の周回もなく周期2の周回もない」「周期2の周回はあるが、他に周期3以上奇数の周回が存在する」場合は解無し。

int N;
int P[101010];
int vis[101010];
vector<int> S;
vector<pair<int,int> > PP;
vector<vector<int> > M;
int path[101010];

int dfs(int cur,int pos) {
	if(vis[cur]) return pos;
	path[pos]=cur;
	vis[cur]=1;
	return dfs(P[cur],pos+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i+1];
	
	int odd=0;
	for(i=1;i<=N;i++) if(vis[i]==0) {
		x=dfs(i,0);
		if(x==1) S.push_back(path[0]);
		else if(x==2) PP.push_back({path[0],path[1]});
		else {
			vector<int> v;
			FOR(y,x) v.push_back(path[y]);
			M.push_back(v);
			odd += x%2;
		}
	}
	
	if(S.size()) {
		_P("YES\n");
		for(i=1;i<S.size();i++) _P("%d %d\n",S[0],S[i]);
		FORR(r,PP) {
			_P("%d %d\n",S[0],r.first);
			_P("%d %d\n",S[0],r.second);
		}
		FORR(r,M) FORR(v,r) _P("%d %d\n",S[0],v);
	}
	else if(PP.size() && odd==0) {
		_P("YES\n");
		_P("%d %d\n",PP[0].first,PP[0].second);
		for(i=1;i<PP.size();i++) {
			_P("%d %d\n",PP[0].first,PP[i].first);
			_P("%d %d\n",PP[0].second,PP[i].second);
		}
		FORR(r,M) {
			for(i=0;i<r.size();i+=2) {
				_P("%d %d\n",PP[0].first,r[i]);
				_P("%d %d\n",PP[0].second,r[i+1]);
			}
		}
	}
	else {
		_P("NO\n");
	}
	
}

まとめ

皆色々(誤った)アプローチを取っていてHackしがいがありました。
自分は結構解にたどり着くのに苦労したのだけど、だいぶpretest通過が多かったのは単にpretestが甘かっただけ？