208 Firetruck(****)

/*
推荐：四星。
题意：求从消防站到火场路径有多少，并逐个输出
思路：深度搜索，状态存储
结果程序运行超时
可能存在数据，起点和终点不连通，但起点周围是一个稠密图。
这样会导致程序无解，但耗时很大。
如果可以先把那些可以到达终点的节点找出来，再在其中进行搜索就可避免！
解法一：通过深度搜索找出
解法二：通过并查集
解法三：tarjan算法，未解决。。。
*/


//错误代码：
#include <cstdio>
#include <cstring>
bool G[25][25],visit[25];
int path[25],n,res;
void dfs(int k,int cur)
{
	if(k==n)
	{
		res++;
		for(int i=1;i<cur;i++)
		{
			if(i!=1)
				printf(" ");
			printf("%d",path[i]);
		}
		printf("\n");
		return;
	}
	for(int i=1;i<=21;i++)
		if(G[k][i] && !visit[i])
		{
			visit[i]=1;
			path[cur]=i;
			dfs(i,cur+1);
			visit[i]=0;
		}
}
int main()
{
	freopen("data.in","r",stdin);
	int cas=1;
	while(scanf("%d",&n)==1)
	{
		int a,b;
		res=0;
		memset(G,0,sizeof(G));
		while(scanf("%d%d",&a,&b)==2)
			if(a==0 && b==0)
				break;//原来这里漏掉了break，结果导致不按想法输出
			else
				G[a][b]=G[b][a]=1;
		memset(visit,0,sizeof(visit));
		path[1]=1;
		visit[1]=1;
		printf("CASE %d:\n",cas++);
		dfs(1,2);
		printf("There are %d routes from the firestation to streetcorner %d.\n",res,n);
	}
	return 0;
}

/*
解法一：深度搜索，使用数组path做存储
*/

#include <cstdio>
#include <cstring>
#include <cstdlib>
bool G[25][25],visit[25];
int m,path[25];
int A[25];
int n,fire;
void init(int u)
{
	visit[u]=1;
	path[m++]=u;
	for(int i=1;i<25;i++)
	{
		if(G[u][i] && !visit[i])
			init(i);
	}
}
int cmp(const void *a,const void *b)
{
	int *pa=(int *)a;
	int *pb=(int *)b;
	return *pa-*pb;
}
void dfs(int node,int dep)
{
	if(node==fire)
	{
		n++;
		for(int i=1;i<dep;i++)
		{
			if(i!=1)
				printf(" ");
			printf("%d",A[i]);
		}
		printf("\n");
		return;//error#1:
	}
	for(int i=0;i<m;i++)
	{
		if(G[node][path[i]] && !visit[path[i]])
		{
			visit[path[i]]=1;
			A[dep]=path[i];
			dfs(path[i],dep+1);
			visit[path[i]]=0;
		}
	}
}
int main()
{
	//freopen("data.in","r",stdin);
	int u,v,cas;
	cas=1;
	while(scanf("%d",&fire)==1)
	{
		memset(G,0,sizeof(G));
		while(scanf("%d %d",&u,&v)==2)
		{
			if(u==0 && v==0) break;
			G[u][v]=G[v][u]=1;
		}
		memset(visit,0,sizeof(visit));
		m=0;
		init(fire);
		qsort(path,m,sizeof(path[0]),cmp);
		memset(visit,0,sizeof(visit));
		visit[1]=1;
		A[1]=1;
		n=0;
		printf("CASE %d:\n",cas++);
		dfs(1,2);
		printf("There are %d routes from the firestation to streetcorner %d.\n",n,fire);
	}
	return 0;
}

/*
解法三：并查集，使用father数组做存储
*/

#include <cstdio>
#include <cstring>
#include <cstdlib>
bool G[25][25],visit[25];
int path[25],m;
int A[25];
int father[25];
int n,fire;
int find(int u)
{
	return father[u]==u?u:father[u]=find(father[u]);
}
int cmp(const void *a,const void *b)
{
	int *pa=(int *)a;
	int *pb=(int *)b;
	return *pa-*pb;
}
void dfs(int node,int dep)
{
	if(node==fire)
	{
		n++;
		for(int i=1;i<dep;i++)
		{
			if(i!=1)
				printf(" ");
			printf("%d",A[i]);
		}
		printf("\n");
		return;//error#1:
	}
	for(int i=0;i<m;i++)
	{
		if(G[node][path[i]] && !visit[path[i]])
		{
			visit[path[i]]=1;
			A[dep]=path[i];
			dfs(path[i],dep+1);
			visit[path[i]]=0;
		}
	}
}
int main()
{
	//freopen("data.in","r",stdin);
	int u,v;
	int cas=1;
	while(scanf("%d",&fire)==1)
	{
		memset(G,0,sizeof(G));
		while(scanf("%d %d",&u,&v)==2)
		{
			if(u==0 && v==0) break;
			G[u][v]=G[v][u]=1;
		}
		for(int i=1;i<25;i++)
			father[i]=i;
		for(int i=1;i<25;i++)
			for(int j=i+1;j<25;j++)
				if(G[i][j] &&find(i)!=find(j))
					father[find(i)]=find(j);
		m=0;
		for(int i=1;i<25;i++)
			if(find(i)==find(fire))
				path[m++]=i;
		qsort(path,m,sizeof(path[0]),cmp);
		memset(visit,0,sizeof(visit));
		visit[1]=1;
		A[1]=1;
		n=0;
		printf("CASE %d:\n",cas++);
		dfs(1,2);
		printf("There are %d routes from the firestation to streetcorner %d.\n",n,fire);
	}
}