Codeforces #161 Div2. C. Circle of Numbers

#161は本参加でなく練習だけなので、これも練習。
http://codeforces.com/contest/263/problem/C

N個の点に対して2N個の辺が与えられる。
このN点が閉路になっており、かつ「隣接点および隣接点の隣接点に辺が張られている」という点の並びが取れるグラフなら、そのような点の並びを出力する。
N点で2N辺あるので、各点は4つの辺に接続されている。

今見ている点をC、１つ前の点をP1、２つ前の点をP2とする。
Cに接続されている他の点をA,Bとすると、このグラフが題意を満たす閉路になっており、AがCの次の隣接点、BがCの次の次の隣接点とするなら、以下を確認すればよい。

• AはP1,P2ではない(逆流を防ぐ)
• AとBは接続されている
• AはP1とBに接続されている(BとP1は接続されないので、AとBどちらがCの隣接点でどちらが隣接点の隣接点かわかる)

この問題は開始の点を問わないので、開始点を1に固定し、１つ前の点の候補と２つ点の前の候補の組み合わせごとに上記ループを回すと、候補点の組み合わせは4*3=12通りで、あとはほぼO(N)で処理できる。

int N;
vector<int> A[100001];
int path[100001];

int subok(int fpre, int fpre2) {
	int cur=0;
	int i,j,k,l,c,s1,s2,s22,pre,pre2;
	int vis[100001];
	ZERO(vis);
	pre=fpre; pre2=fpre2;
	//1周目
	FOR(i,N) {
		path[i]=cur;
		vis[cur]=1;
		c=-1;
		if(i>=N-1) vis[0]=0;
		if(i==N-2 && cur!=fpre2) return 0;
		if(i==N-1 && cur!=fpre) return 0;
		
		FOR(j,A[cur].size()) {
			s1 = A[cur][j];
			if(s1==pre || s1==pre2 || vis[s1]) continue;
			int ok=0;
			FOR(l,A[s1].size()) if(A[s1][l]==pre) ok|=2;
			
			FOR(k,A[cur].size()) {
				if(j==k) continue;
				s2=A[cur][k];
				FOR(l,A[s1].size()) if(A[s1][l]==s2) ok|=1;
			}
			if(ok==3) {
				c=s1;
				break;
			}
		}
		if(c==-1) return 0;
		pre2=pre;
		pre=cur;
		cur =c;
	}
	
	return 1;
}

int ok() {
	int i,j;
	
	FOR(i,4) FOR(j,4) if(i!=j && subok(A[0][i],A[0][j])) {
		FOR(i,N) {
			if(i>0) _P(" ");
			_P("%d",path[i]+1);
		}
		_P("\n");
		return 1;
	}
	return 0;
}

void solve() {
	int f,r,i,j,k,l;
	
	N=GETi();
	FOR(i,2*N) {
		j=GETi()-1;
		k=GETi()-1;
		A[j].push_back(k);
		A[k].push_back(j);
	}
	FOR(i,N) {
		if(A[i].size()!=4) {
			_P("-1\n");
			return;
		}
	}
	
	if(ok()) return;
	_P("-1\n");
	
	return;
}

まとめ

他の回答や解説もおおむね方針は一致しているようだ。
ただみんなコードが長め。もうちょいシンプルな回答はないものか…