记录编号	178385	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO DEC13]虫洞	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.464 s
提交时间	2015-08-13 19:58:42	内存使用	0.30 MiB

/*
ID: jhqwan1
PROG: wormhole
LANG: C++11
*/
//#define debug
//初始BUG: 1.ysetnum不是已序序列，不能调用lower_bound；2.搜索配对时有重复。 
#include <fstream>
#include <iostream>
#include <algorithm>
#include <set>
#include <cstdlib>

using namespace std;
typedef set<unsigned int> uiset;

ifstream fin("wormhole.in");
ofstream fout("wormhole.out");
const unsigned int MAXN(13);
unsigned int n,ans=0,x[MAXN],y[MAXN],line[MAXN],ysetnum[MAXN],cnty=0;
//修复bug2 
void dfs(unsigned int, unsigned int, unsigned int), search();
bool zhan[MAXN] = {false};
uiset everyy[MAXN];

main()
{
	fin >> n;
	for (unsigned int i = 1; i <= n; ++i){
		fin >> x[i] >> y[i];
#ifdef debug
		cout << x[i] << ' ' << y[i] << endl;
#endif
		unsigned int j;
		for (j = 1; j <= cnty; ++j)
			if (y[i] == ysetnum[j]){
				everyy[j].insert(x[i]);
				break;
			}
		if (j > cnty){
			ysetnum[++cnty] = y[i];
			everyy[cnty].insert(x[i]);
		}
#ifdef debug
		cout << "cnty = " << cnty << ".\n";
#endif
	}
	fin.close();
	
	//修复bug2 
	dfs(1ul, 0ul, 0ul);
	
	fout << ans << endl;
	fout.close();
#ifdef debug
	system("fc wormhole.ans wormhole.out");
	system("pause");
	system("type wormhole.in");
	system("pause");
#endif
}

//修复bug2 
void dfs(unsigned int x, unsigned int la, unsigned int lad){
#ifdef debug
	cout << "x = " << x << ";\tla = " << la << ".\n";
#endif
	//修复bug2 
	unsigned start;
	if (la == 0)
		start = lad + 1;
	else
		start = la + 1;
	for (unsigned int i = start; i <= n; ++i)
		if (! zhan[i]){
#ifdef debug
			cout << "i = " << i << ".\n";
#endif
			unsigned int nxt, nxd;
			zhan[i] = true;
			if (x & 1ul){
				nxt = i;
				nxd = i;
			}
			else{
				line[la] = i;
				line[i] = la;
				nxt = 0;
				nxd = lad;
			}
#ifdef debug
			cout<<"x = "<<x<<";\tnxt = "<<nxt<<";\tnxd = "<<nxd<<".\n";
#endif
			if (x == n){
				search();
#ifdef debug
				cout << "now ans = " << ans << ".\n";
#endif
			}
			else
				dfs(x + 1, nxt, nxd);
			zhan[i] = false;
		}
}

void search(){
#ifdef debug
	cout << "line:";
	for (unsigned int i = 1; i <= n; ++i)
		cout << line[i] << ' ';
	cout << endl;
#endif
	bool yes = false, had[MAXN];
	unsigned int cnt;
	for (unsigned int i = 1; i <= n && (! yes); ++i){
		fill(had + 1, had + n + 1, false);
		unsigned int nhole = i;
		do{
#ifdef debug
			cout << "nhole = " << nhole << ".\n";
#endif
			had[nhole] = true;
			nhole = line[nhole];
#ifdef debug
			cout << "nhole = " << nhole << ".\n";
#endif
			//修复bug1 
			unsigned int ys=find(ysetnum+1,ysetnum+n+1,y[nhole])-ysetnum;
#ifdef debug
			cout<<"ys = "<<ys<<";\tysetnum[ys] = "<<ysetnum[ys]<<".\nx[nhole] ";
			cout << "= " << x[nhole] << ".\n";
#endif
			if (everyy[ys].find(x[nhole]) != --everyy[ys].end()){
				unsigned int ny=ysetnum[ys],nx=*(++everyy[ys].find(x[nhole]));
#ifdef debug
				cout << "ny = " << ny << ";\tnx = " << nx << ".\n";
#endif
				for (unsigned int j = 1; j <= n; ++j)
					if (nx == x[j] && ny == y[j]){
						nhole = j;
#ifdef debug
						cout<<"nhole = "<<nhole<<";\tx[nhole] = "<<x[nhole];
						cout << ";\ty[nhole] = " << y[nhole] << ".\n";
#endif
						break;
					}
				if (had[nhole]){
					yes = true;
					break;
				}
			}
			else
				break;
		}while(1);
		if (yes)
			break;
		else
			continue;
	}
	if (yes)
		ans++;
}