Codeforces #192 Div1. C. Graph Reconstruction

さてC。
このグラフ構築問題はいかにもCodeforces。
http://codeforces.com/contest/329/problem/C

問題

各点に最大2辺があるグラフが与えられる。

点の数と辺の数が同じで、各点が接続される辺は2本以下であり、かつ元のグラフで張られていた点同士の間の辺が張られていないようなグラフを構築せよ。

解法

まず、元のグラフを連結成分ごとにグループ化する。
異なるグループ同士の点は連結してよく、同じグループでも隣接しない点は連結してよい。
よって、以下の手順で処理すればよい。

各グループXは、X0,X1,X2,,,のように連結しているとする。

最大グループのサイズが全体の半分以下の場合を考える。
たとえば12個の点が3点のA、4点のB、5点のCの場合を考える。
この時はCの間にAとBの要素を挟んでいけばよい。以下のようにA0,A1,A2,B0,B1,B2,B3をC0～C4の間に順にはさめる。
C0,A0,B2,C1,A1,B3,C2,A2,C3,B0,C4,B1

最大グループのサイズが半分以上の場合、かつ5以上の場合を考える。
グループDの数が過半数である場合、D0,D1,D2,D3,D4,D5,,,,とあったら、偶数番目を先に並べ、奇数番目を後に並べてD0,D2,D4,D6,,,,D1,D3,D5,,,,と並べればよい。
そしてその間に、また他のグループの要素を並べていけばよい。

どちらも満たさない場合、つまり最大グループのサイズが半分以上で5未満の場合、点の数が高々8なので総当たりで調べる。

int N,M;
vector<int> E[100001];
vector<pair<int, vector<int> > > V;
int vis[100001];
int mat[10][10];
vector<int> R,R2;
vector<int> S;

void dfs(int cur,vector<int>& VE) {
	int i;
	vis[cur]=1;
	VE.push_back(cur);
	FOR(i,E[cur].size()) if(vis[E[cur][i]]==0) dfs(E[cur][i],VE);
}

int connect(vector<int>& VE) {
	int i;
	int cur=VE[0];
	FOR(i,E[VE[0]].size()) if(E[VE[0]][i]==VE[VE.size()-1]) return 1;
	return 0;
}

void dfs2(int cur, int mask, int left) {
	int i,s=S.size();
	
	S.push_back(cur);
	if(left==0 || (left==1 && N==M)) {
		if(left==1 && N==M) {
			if(mat[S[S.size()-1]][1]) return;
			S.push_back(1);
		}
		FOR(i,S.size()-1) _P("%d %d\n",S[i],S[i+1]);
		exit(0);
	}
	
	FOR(i,N) {
		if(mask & (1<<i)) continue;
		if(mat[cur][i+1]) continue;
		dfs2(i+1,mask | (1<<i),left-1);
	}
	S.resize(s);
}


void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
		if(N<10) mat[x][y]=mat[y][x]=1;
	}
	
	FOR(i,N) {
		if(vis[i+1]==0 && E[i+1].size()==1) {
			vector<int> VV;
			dfs(i+1,VV);
			V.push_back(make_pair(VV.size(),VV));
		}
	}
	FOR(i,N) {
		if(vis[i+1]==0) {
			vector<int> VV;
			dfs(i+1,VV);
			V.push_back(make_pair(VV.size(),VV));
		}
	}
	
	sort(V.begin(),V.end());
	vector<int> VL=V[V.size()-1].second;
	vector<vector<int> > V2;
	FOR(i,V.size()-1) V2.push_back(V[i].second);
	
	k=VL.size();
	FOR(j,V.size()-1) FOR(i,V[j].first) R2.push_back(V[j].second[i]);
	if(k<N-k || (k==N-k+1 && !connect(VL))) {
		FOR(i,k) {
			R.push_back(VL[i]);
			for(j=i;j<R2.size();j+=k) R.push_back(R2[j]);
		}
		
		FOR(i,M) _P("%d %d\n",R[i],R[(i+1)%N]);
		return;
	}
	
	if(k>=5) {
		if(k%2==0) swap(VL[VL.size()-1],VL[VL.size()-3]);
		FOR(i,k) {
			if(k%2==0) {
				if(i*2<k) R.push_back(VL[i*2]);
				else R.push_back(VL[i*2-k+1]);
			}
			else {
				R.push_back(VL[(i*2)%k]);
			}
			for(j=i;j<R2.size();j+=k) R.push_back(R2[j]);
		}
		FOR(i,M) _P("%d %d\n",R[i],R[(i+1)%N]);
		return;
	}
	
	FOR(i,N) {
		S.clear();
		dfs2(i+1,1<<i,M);
	}
	_P("-1\n");
}

まとめ

本番のあと自力で解けたけど、えらい場合分けに手間取った。
Editorial見ても結構複雑だな…。