題目：

給出一個結點d和一個無向圖中所有的邊，按字典序輸出這個無向圖中所有從1到d的路徑。

思路：

1.看到紫書上的提示，如果不預先判斷結點1是否能直接到達結點d，上來就直接dfs搜索的話會超時，于是就想到了用并查集來預先判斷是否屬于同一個連通分量。

2.可以將與d屬于同一個連通分量的點用一個數組保存起來，然后dfs搜索這個數組就可以了，這也就是只搜索了與d在一個連通分量里的點。

3.當搜索到d的時候就輸出路徑。

代碼：

#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define MAX 1e3 #define FRE() freopen("in.txt","r",stdin) #define FRO() freopen("out.txt","w",stdout) using namespace std; typedef long long ll; const int maxn = 22; bool mp[maxn][maxn]; int fa[maxn],d,lk[maxn],vis[maxn]; int idx,path[maxn],cnt;void init(){for(int i=0; i<maxn; i++){fa[i] = i;}memset(lk,0,sizeof(lk));memset(vis,0,sizeof(vis));memset(mp,0,sizeof(mp));memset(path,0,sizeof(path)); }int _find(int x){//并查集查找祖先return fa[x]==x ? x : fa[x] = _find(fa[x]); }void mergeNode(int x,int y){//合并不屬于同一個連通分量的兩個點int tx = _find(x),ty = _find(y);if(tx != ty){fa[tx] = ty;} }bool isLinked(int x,int y){//判斷兩個點是不是屬于同一個連通分量if(_find(x)!=_find(y)){return false;}return true; }void DFS(int now, int MX){if(now==d){//搜索到d就輸出；路徑cnt++;printf("1");for(int i=0; i<MX; i++){printf(" %d",path[i]);}printf("\n");}else{//cout<<now<<endl;for(int i=1; i<idx; i++){int u = lk[i];if(!vis[u] && mp[now][u]){vis[u] = true;path[MX] = u;//這里其實沒必要另開一個數組保存路徑，在下一個循環的時候當前的路徑已經輸出或沒用了DFS(u,MX+1);vis[u] = false;}}} }void check(){for(int i=0; i<idx; i++){printf("%d ",lk[i]);}printf("\n"); }int main(){//FRE();int kase=0;while(scanf("%d",&d)!=EOF){int st,en;init();while(scanf("%d%d",&st,&en)&&st){mp[st][en] = 1;mp[en][st] = 1;mergeNode(st,en);}printf("CASE %d:\n",++kase);if(isLinked(1,d)==false){printf("There are 0 routes from the firestation to streetcorner %d.\n",d);}else{idx=0;for(int i=1; i<maxn; i++){//找到與d在同一個連通分量里邊的點并保存if(isLinked(i, d)){lk[idx++] = i;}}sort(lk,lk+idx);//從小到大排序，保證字典序//check();cnt = 0;DFS(1, 0);printf("There are %d routes from the firestation to streetcorner %d.\n",cnt,d);}}return 0; }

?

轉載于:https://www.cnblogs.com/sykline/p/10325726.html

總結

以上是生活随笔為你收集整理的UVA - 208 Firetruck（并查集+dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。