題干：

為了訓(xùn)練小希的方向感，Gardon建立了一座大城堡，里面有N個房間(N<=10000)和M條通道(M<=100000)，每個通道都是單向的，就是說若稱某通道連通了A房間和B房間，只說明可以通過這個通道由A房間到達(dá)B房間，但并不說明通過它可以由B房間到達(dá)A房間。Gardon需要請你寫個程序確認(rèn)一下是否任意兩個房間都是相互連通的，即：對于任意的i和j，至少存在一條路徑可以從房間i到房間j，也存在一條路徑可以從房間j到房間i。?

Input

輸入包含多組數(shù)據(jù)，輸入的第一行有兩個數(shù)：N和M，接下來的M行每行有兩個數(shù)a和b，表示了一條通道可以從A房間來到B房間。文件最后以兩個0結(jié)束。?

Output

對于輸入的每組數(shù)據(jù)，如果任意兩個房間都是相互連接的，輸出"Yes"，否則輸出"No"。?

Sample Input

3 3 1 2 2 3 3 1 3 3 1 2 2 3 3 2 0 0

Sample Output

Yes No

解題報告：

? ? 這題做法很多，也可以直接暴力跑每個節(jié)點(diǎn)是否可以連通其他節(jié)點(diǎn)，也可以直接跑tarjan算法看是否只有一個強(qiáng)連通分量。

?

AC代碼：

#include<cstdio> #include<stack> #include<algorithm> #include<cstring> #include<iostream> using namespace std; const int MAXN = 10000 + 5; const int MAXM = 100000 + 5; int n,m; int top,tot,cnt; int head[MAXN]; bool vis[MAXN]; int dfn[MAXN],low[MAXN]; stack<int> sk; struct Edge {int to,ne; }e[MAXM]; void add(int u,int v) {e[++top].to = v;e[top].ne = head[u];head[u] = top; } void tarjan(int x) {low[x] = dfn[x] = ++tot;sk.push(x);vis[x] = 1;for(int i = head[x]; i!=-1; i=e[i].ne) {int v = e[i].to;if(dfn[v] == 0) {tarjan(v);low[x] = min(low[x],low[v]);}else if(vis[v] == 1) {low[x] = min(low[x],dfn[v]);}}if(low[x] == dfn[x]) {cnt++;while(1) {int now = sk.top();sk.pop();vis[now]=0;if(now == x) break;}}} int main() {int a,b;while(~scanf("%d%d",&n,&m)) {if(n == 0 && m == 0) break;top = tot = cnt = 0;while(sk.size()) sk.pop();memset(head,-1,sizeof head);memset(vis,0,sizeof vis);for(int i = 1; i<=n; i++) dfn[i] = low[i] = 0;for(int i = 1; i<=m; i++) {scanf("%d%d",&a,&b);add(a,b);}for(int i = 1; i<=n; i++) {if(dfn[i] == 0) tarjan(i);}if(cnt == 1) puts("Yes");else puts("No");}return 0 ; }

直接暴力AC代碼2：

//hdu1269(迷宮城堡&&判斷有向圖是否聯(lián)通) //題目大意：已知有n(n<=10000)個點(diǎn)，M(M<=100000)個道路。每條道路都是單向的。求任意兩個點(diǎn)之間是否聯(lián)通？ //解題思路：由于點(diǎn)n的范圍較大，所以用鄰接表存儲n個點(diǎn)的道路情況。然后依次搜索n各點(diǎn)能否 //到達(dá)剩余的n-1個點(diǎn)。如果有一個不滿足，就退出循環(huán)。表示該有向圖不是聯(lián)通圖。否則就是。 //這里我用的是dfs搜索看是否某個點(diǎn)能否到達(dá)其余的n-1個點(diǎn)。 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,head[100010],k,flag,vis[10010],cnt,gg; struct node {int x,y;int next; } edge[100010]; void init() { //初始化鄰接表k=0;memset(head,-1,sizeof(head)); } void input() { //讀取數(shù)據(jù)init();int i,j,x,y;for(i=0; i<m; i++) {scanf("%d%d",&x,&y);edge[k].x=x;edge[k].y=y;edge[k].next=head[x]; //建x到y(tǒng)的邊。head[x]=k++;} } void dfs(int x) {int v,i;if(cnt==n-1) {//可以到達(dá)其余的n-1個點(diǎn)gg=1;return; } for(i=head[x]; i!=-1; i=edge[i].next) {v=edge[i].y;if(!vis[v]) {vis[v]=1;cnt++; //cnt用來記錄從某點(diǎn)出發(fā)所能到達(dá)的點(diǎn)數(shù)dfs(v);if(gg) return;}} } int main() {int i,j;while(scanf("%d%d",&n,&m)&&(n|m)) {input();flag=1;for(i=1; i<=n; i++) {cnt=0;gg=0;memset(vis,0,sizeof(vis));vis[i]=1; //標(biāo)記idfs(i); //搜索i所能到達(dá)的點(diǎn)的個數(shù)。if(cnt<n-1) {flag=0;break; //有一個點(diǎn)到其余各點(diǎn)不是n-1時，則該圖不聯(lián)通。} //退出循環(huán)}if(flag==1) printf("Yes\n");else printf("No\n");}return 0; }

新的算法（kosaraju算法）：（https://blog.csdn.net/qq7366020/article/details/12943345）

//Final kosaraju判斷有向圖是否為強(qiáng)聯(lián)通圖 #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX 10100 struct snode{int to,next; }edge1[MAX*30],edge2[MAX*30],edge3[MAX*30]; int visit1[MAX],In[MAX],To[MAX],pre1[MAX],pre2[MAX],Index1,Index2,k,list[MAX]; int father[MAX]; void Add_edge1(int a,int b) //建立正向圖 {edge1[Index1].to=b,edge1[Index1].next=pre1[a];pre1[a]=Index1++; }void Add_edge2(int a,int b) //建立逆向圖 {edge2[Index2].to=b,edge2[Index2].next=pre2[a];pre2[a]=Index2++; }void Kosaraju(int u) //第一次正向圖搜索 {int i,v;for(i=pre1[u];i!=-1;i=edge1[i].next){v=edge1[i].to;if(visit1[v]==0){visit1[v]=1;Kosaraju(v);}}list[k++]=u; }void DFS(int u,int Father) //第二次逆向圖搜索 {int i,v;visit1[u]=2;father[u]=Father;for(i=pre2[u];i!=-1;i=edge2[i].next){v=edge2[i].to;if(visit1[v]==1)DFS(v,Father);} }int main() {int n,m,i,j,a,b,c,pd;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0)break;Index1=Index2=0;memset(In,0,sizeof(In));memset(pre1,-1,sizeof(pre1));memset(pre2,-1,sizeof(pre2));memset(visit1,0,sizeof(visit1));memset(father,0,sizeof(father));for(i=0;i<m;i++){scanf("%d%d",&a,&b);Add_edge1(a,b);Add_edge2(b,a);}for(i=1,k=0;i<=n;i++){if(!visit1[i]){visit1[i]=1;Kosaraju(i);}}for(j=k-1,c=0;j>=0;j--) //第二次搜索和第一次搜索頂點(diǎn)的順序一樣{if(visit1[list[j]]==1){DFS(list[j],++c);}}for(i=1,pd=0;i<n;i++) //有兩個聯(lián)通塊就說明不是聯(lián)通圖if(father[i]!=father[i+1])pd=1;if(pd==0)printf("Yes\n");elseprintf("No\n");}return 0; }

其實(shí)這題還是可以用并查集做的AC代碼：（https://blog.csdn.net/wyjwyl/article/details/49369085）

#include<cstdio> #include<cstring> #define maxn 10000+10 int rec[3][maxn]; int n,m; void init() {for(int i=1;i<=2;++i){for(int j=1;j<=n;++j)rec[i][j]=j;} } int find(int x,int i) {return x==rec[i][x]?x:rec[i][x]=find(rec[i][x],i); } void merge(int a,int b) {if(a!=n){int fa=find(a,1);int fb=find(b,1);if(fa!=fb)rec[1][a]=b;//合并到后面的那個元素身上}if(b!=n){int fa=find(a,2);int fb=find(b,2);if(fa!=fb)rec[2][b]=a;//合并到前面的那個元素上} } int main() {int a,b;while(scanf("%d%d",&n,&m)&&(n||m)){int flag=1;init();for(int i=1;i<=m;++i){scanf("%d%d",&a,&b);merge(a,b);}for(int i=1;i<=n;++i){if(find(i,1)!=n||find(i,2)!=n){flag=0;break;}}if(flag)puts("Yes");elseputs("No");}return 0; }

超時代碼：

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std; const int MAXN = 10000 + 5; const int MAXM = 100000 + 5; int n,m; int top,flag; int head[MAXN]; bool vis[MAXN]; struct Edge {int to,ne;}e[MAXM]; void add(int u,int v) {e[++top].to = v;e[top].ne = head[u];head[u] = top; } void dfs(int x,int cnt) {if(x == 1 && cnt == n+1) { // for(int i = head[x]; i!=-1; i=e[i].ne) { // if(e[i].to == 1) { // flag =1;break; // } // }flag=1;return ;}for(int i = head[x]; i!=-1; i=e[i].ne) {if(vis[e[i].to] && e[i].to != 1) continue;vis[e[i].to]=1;dfs(e[i].to,cnt+1);if(flag) return;vis[e[i].to] = 0;} } int main() {int a,b;while(~scanf("%d%d",&n,&m)) {if(n == 0 && m == 0) break;top = flag = 0;memset(head,-1,sizeof head);memset(vis,0,sizeof vis);for(int i = 1; i<=m; i++) {scanf("%d%d",&a,&b);add(a,b);}dfs(1,1);if(flag) puts("Yes");else puts("No");}return 0 ; }

總結(jié)：?這件事情告訴我們一個道理。。。。不帶回溯的dfs要比帶回溯的dfs快的多的多的多，因?yàn)椴粠Щ厮莸氖且槐閛n，帶回溯的是n！

總結(jié)

以上是生活随笔為你收集整理的【HDU - 1269】迷宫城堡 （tarjan算法模板）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。