Codeforces 161C (263C) Circle of Numbers

問題

円周上に1〜nの数が並んでいる。
隣り合う数同士および、二つ隣の数同士が弧で結ばれている。

今、弧がどの数字とどの数字を結んでいるかが与えられる。
このとき、円周上に元の数字がどのような順で並んでいたかを復元せよ。
答えが複数ある場合はどれを出力してもよく、答えが存在しない場合は-1を出力せよ。

制約条件

n≦10^5

方針

全部の数の次数は4としてよい。そうでない場合は-1.
n≧7のとき、
ある数xと弧で結ばれている数をa, b, c, dとする
すると、xの隣にくるのは、a, b, c, dのうち、お互いが弧で結ばれているもの二つ。
（a, cが弧で結ばれているとしたら、a x cと隣り合うはず）

これで、すべての数の隣接関係がわかるので、順番に並べればよい。
n≦6のときは、全探索してよい。

というのが多分模範解答。
答えが作れる場合は一瞬で答えができるので、普通にDFSして、
1.9s以内に答えを作れなかったら、-1を出すという方針で通った。

ソースコード

double getnow(){
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return tv.tv_sec + tv.tv_usec * 1e-6;
}

int n;
set<int> e[100000];
double now;
vi ans;
set<int> u;

void rec(int c){
	if(getnow() - now > 1.95){
		cout << -1 << endl;
		exit(0);
	}
	
	if(ans.size() > 1 && !e[ans[ans.size() - 2]].count(c)) return;
	ans.pb(c);
	u.insert(c);
	
	if(ans.size() == n){
		rep(i, n) cout << ans[i] + 1 << (i==n-1?"\n":" ");
		exit(0);
	}
	each(i, e[c]) if(!u.count(*i)){
		each(j, e[*i]){
			if(!e[c].count(*j)) continue;
			if(ans.size() < n - 1 && u.count(*j)) continue;
			if(ans.size() == n - 1 && *j != ans[0]) continue;
			rec(*i);
		}
	}
	ans.pop_back();
	u.erase(c);
}
int p[100000];
int root(int x){
	if(p[x] < 0) return x;
	return p[x] = root(p[x]);
}

int main(){
	now = getnow();
	memset(p, -1, sizeof(p));
	cin >> n;
	rep(i, 2 * n){
		int a, b;
		cin >> a >> b;
		a--; b--;
		e[a].insert(b);
		e[b].insert(a);
		
		int x = root(a), y = root(b);
		if(x != y){
			p[x] += p[y];
			p[y] = x;
		}
	}
	rep(i, n) if(root(i) != root(0) || e[i].size() != 4) goto FAIL;
	rec(0);
	FAIL:
	cout << -1 << endl;
	return 0;
}