Firetruck UVA

怎么输出路径？用DFS，因为递归是出栈和入栈的过程。这道题长知识了！

为了按字典序输出，所以对邻接表进行一次排序！

并查集也是预处理，某个点和终点不在同一个集合中时，就不处理！

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<vector>
 6 using namespace std;
 7 
 8 const int maxn=1000;
 9 vector<int> G[maxn];
10 
11 int en,last,ans;
12 int way[21],Fa[21],vis[21];
13 
14 int Find(int x){
15     if(x!=Fa[x]) Fa[x]=Find(Fa[x]);
16     return Fa[x];
17 }
18 
19 void Union(int a,int b){
20     int x=Find(a),y=Find(b);
21     if(x==y) return;
22     else Fa[x]=y; 
23 }
24 
25 void DFS(int x,int cnt)                   //  good
26 {    
27     if(x==en){
28         cout<<1;
29         for(int i=1;i<cnt;i++) printf(" %d",way[i]);
30         puts("");   //等价于 cout<<endl;
31         ans++;
32     }
33     for(int i=0;i<G[x].size();i++){
34         if(vis[G[x][i]]&&Find(G[x][i])==last){
35             vis[G[x][i]]=false;
36             way[cnt]=G[x][i];
37             DFS(G[x][i],cnt+1);
38             vis[G[x][i]]=true;
39         }
40     }
41 }
42 
43 int main()
44 {   int cases=0;
45     while(cin>>en){
46         int x,y;
47         for(int i=1;i<=21;i++) Fa[i]=i;
48         for(int i=1;i<=21;i++) G[i].clear();    //不要忘了！ 
49         while(~scanf("%d%d",&x,&y)){
50             if(x==0&&y==0) break;
51             G[x].push_back(y);
52             G[y].push_back(x);
53             Union(x,y);
54         }
55         
56         printf("CASE %d:
",++cases);
57         for(int i=1;i<=21;i++) sort(G[i].begin(),G[i].end());   // key point!!!! 
58         memset(vis,true,sizeof(vis));
59         ans=0;
60         way[1]=1;
61         vis[1]=false;
62         last=Find(en);
63         
64         if(Find(1)==last) DFS(1,1);
65         printf("There are %d routes from the firestation to streetcorner %d.
",ans,en); 
66     }
67     return 0;
68 }