Firetruck UVA - 208

DFS+并查集

如果只用DFS的话会超时，用并查集剪枝，和起点终点不联通的点就不用跑了

这题有好多人写了博客，但是我觉得我的代码写的比较通俗易懂所以就贴上来了，我觉得我写代码的目标就是让任何人都能看懂，越小白越好（其实是因为真小白吧……

#include<bits/stdc++.h>
using namespace std;
int E[30][30];
int diste;
int mark[30];
int path[30];
int fin[30];
int ans;
int root[30];
void init()  
{  for(int i=1;i<=21;i++)  root[i] = i;  
}  
int find(int p)  
{  int t;  int child = p;  while(p != root[p])  p = root[p];  while(child != p)  {  t = root[child];  root[child] = p;  child = t;  }  return p;  
}  
void merge(int x, int y)  
{  int fx = find(x);  int fy = find(y);  if(fx != fy)  root[fx] = fy;  
}  
void input()
{memset(E,0,sizeof E);int a,b;while(scanf("%d%d",&a,&b)&&a&&b){E[a][b]=1;E[b][a]=1;  merge(a,b);}
}
void print(int g)
{int q=path[g];int len=0;fin[len++]=g;while(q!=0){fin[len++]=q;q=path[q];}while(len--)printf("%d%c",fin[len],len==0?'\n':' ');
}void DFS(int g)
{    if(g==diste){print(g);ans++;return;}mark[g]=1;for(int a=1;a<=21;a++){if(E[a][g]&&!mark[a]&&find(a)==find(diste)){path[a]=g;DFS(a);    }}mark[g]=0;}int main()
{int t=0;while(scanf("%d",&diste)!=EOF){ans=0;t++;init();input();printf("CASE %d:\n",t);//    for(int i=1;i<=diste;i++)//    cout<<i<<":"<<root[i]<<endl;DFS(1);printf("There are %d routes from the firestation to streetcorner %d.\n",ans,diste);}return 0;
}