USACO 1.4.5_wormhole

/*
ID: cjn77881
LANG: C++
TASK: wormhole
*/ 

#include <stdio.h>

typedef struct WormHole WormHole;
struct WormHole{
	int x,y,next,pair;
	bool v;
};

int N,js,ans,array[12];
WormHole wormhole[12];

void init(){
	for (int i=0;i<N;i++) {
		wormhole[i].next=-1;
		wormhole[i].pair=-1;
	}
	for (int i=0;i<N;i++)
		for (int j=0;j<N;j++)
			if (i!=j){
				if (wormhole[i].y==wormhole[j].y && wormhole[i].x>wormhole[j].x) {
					if (wormhole[j].next == -1) wormhole[j].next = i;
					else if (wormhole[i].x<wormhole[wormhole[j].next].x) wormhole[j].next = i;
				}
			}
	//for (int i=0;i<N;i++) printf("id=%d,x=%d,y=%d, next is %d\n",i,wormhole[i].x,wormhole[i].y,wormhole[i].next);
	return;
}

int dfs(WormHole *a,int p,int depth){
	if (depth>N) return 1; //若搜索深度超过虫洞数，中间必然存在环路 
	if (a[p].next == -1) return 0;
	return dfs(a,a[a[p].next].pair,depth+1); //如果当前虫洞后面还有虫洞，搜索下一虫洞的连接端是否存在环路 
}

int circle(WormHole *a){
	for (int i=0;i<N;i++){ //从任意点出发都没有环路才算是无环路的配对 
		if (dfs(a,i,0)==1) return 1;
	}
	return 0;
}

void solve(WormHole *a,int depth){
	if (depth == N>>1){
		js++;
		ans+=circle(a);
		//for (int i=0;i<N;i++) printf("%d ",array[i]); printf("\n");
	}
	
	int i;
	for (i=0;i<N;i++) if (a[i].pair == -1) break; //！！！找到第一个没有配对的虫洞，为其寻找配对项，不这么做最后结果还是排列组合的 
	for (int j=0;j<N;j++) if (j!=i && a[j].pair==-1){
		a[i].pair = j;
		a[j].pair = i;
		array[depth<<1] = i; array[(depth<<1)+1] = j;
		solve(a,depth+1);
		a[i].pair = -1;
		a[j].pair = -1;
		array[depth<<1] = -1; array[(depth<<1)+1] = -1;
	}
	
	return;
}

int main(){
	
	FILE *fin = fopen("wormhole.in","r");
	FILE *fout = fopen("wormhole.out","w");
	
	fscanf(fin,"%d",&N);
	for (int i=0;i<N;i++) fscanf(fin,"%d %d",&wormhole[i].x,&wormhole[i].y);
	init();
	solve(wormhole,0);
	printf("%d\n",ans);
	fprintf(fout,"%d\n",ans);
	return 0;
}