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

Input

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

Output

對于輸入的每組數據，如果任意兩個房間都是相互連接的，輸出"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

題意很簡單，就是問該圖任意兩點是否能連通，既是否為強連通圖。板子題，tanjar算法看了好久才理解。

參考博客：https://blog.csdn.net/qq_16234613/article/details/77431043

? ? ? ? ? ? ? ? ??https://blog.csdn.net/justlovetao/article/details/6673602

? ? ? ? ? ? ? ? ??https://blog.csdn.net/qq_42211531/article/details/87894285

?? ? ? ?這里說一下自己的理解，該算法通過dfs的思想找出算法中存在的環，如果某個點的出度為0，則該點一定不能與其他點構成環，即是一個單獨強連通分量。我們假設從一點開始找，那么dfn[u]表示從u點被搜索的時刻（時間戳），low[u]表示u點能回溯到最早的棧中節點的次序號。可能low數組比較難理解，但是它的作用就是當u點處于某個點root搜索的子樹中，如果他同時又能連通比u搜到還早的點，那不就構成一個環了嘛。??

? ? ? ? 前邊說tanjar（u）：即時對u點dfs找環停止的條件是u點能搜索的點都搜完了。分為3種情況：

? ? ? ? 第一種就是u點沒有出度，那么該點出棧，自己為一個強連通分量；

? ? ? ? 第二種就是u點的下一個點V沒有被搜索過，那么就tanjar（V）//深搜，同時v點low值與u點low值取最小；

? ? ? ? 第三種就是u點下一個點V被搜索過，但是它還在棧里邊（保證他們處于一個強連通分量），那么他的u點的low值與

v點的dfn值取最小

? ? ? ?棧的作用就是dfs搜索時加入，也就是說里邊所有的元素都是一個樹的元素，在搜索過程中依次把單一的強連通分量剔除。具體就看上邊的博客。

該算法的核心代碼為：

void tanjar(int u)
{low[u]=dfn[u]=++t;//記錄時間戳，一開始low與dfn值一樣Stack[++top]=u;//搜索并入棧inStack[u]=1;//記錄入棧的點for(int i=head[u];i!=-1;i=edge[i].p)//從u點開始搜索，若沒有下個點就直接彈出，對應第一種情況{int v=edge[i].to;if(!dfn[v])//第二種情況，若下一個點沒被搜過，那就接著搜唄，dfs。{tanjar(v);low[u]=min(low[u],low[v]);//比較一哈，可能v點直接連到時間戳為1的點了呢，比如1->2,2->3,但是3卻之間連到1了那么三者low值都得為1}else{if(inStack[v])//第三種情況，下一個被搜過但是在棧內,明顯u點時間戳是靠后的，那么就看一下他最多能回溯到哪個位置low[u]=min(low[u],dfn[v]);//到底為什么是與dfn[v]比較，我覺的可能是記錄一下他屬于哪一個環或者保證了low的定義}}int x;if(low[u]==dfn[u])//這個就是某個強連分量的第一個搜索的點，這個時候棧里邊從top到他自己全是屬于該點為起點搜索的強連通分量。{cnt++;//強連通分量的個數do{x=Stack[top--];inStack[x]=0;}while(u!=x);//出棧最好模擬一下，出棧的循環中止條件為就是把那個u點彈出來為止}
}

ac代碼：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
typedef long long ll;
using namespace std;
const int maxn=1e5+5;
int cnt,n,m,top,sign,t;
int Stack[maxn],inStack[maxn],head[maxn],low[maxn],dfn[maxn];
struct node
{int to,p;
}edge[maxn];
void init()
{top=0;sign=0;cnt=0;t=0;for(int i=0;i<maxn;i++){head[i]=-1;low[i]=0;dfn[i]=0;Stack[i]=0;inStack[i]=0;}
}
void add(int u,int v)
{edge[sign]=node{v,head[u]};head[u]=sign++;
}
void tanjar(int u)
{low[u]=dfn[u]=++t;//記錄時間戳，一開始low與dfn值一樣Stack[++top]=u;//搜索并入棧inStack[u]=1;//記錄入棧的點for(int i=head[u];i!=-1;i=edge[i].p)//從u點開始搜索，若沒有下個點就直接彈出，對應第一種情況{int v=edge[i].to;if(!dfn[v])//第二種情況，若下一個點沒被搜過，那就接著搜唄，dfs。{tanjar(v);low[u]=min(low[u],low[v]);//比較一哈，可能v點直接連到時間戳為1的點了呢，比如1->2,2->3,但是3卻之間連到1了那么三者low值都得為1}else{if(inStack[v])//第三種情況，下一個被搜過但是在棧內,明顯u點時間戳是靠后的，那么就看一下他最多能回溯到哪個位置low[u]=min(low[u],dfn[v]);//到底為什么是與dfn[v]比較，我覺的可能是記錄一下他屬于哪一個環或者保證了low的定義}}int x;if(low[u]==dfn[u])//這個就是某個強連分量的第一個搜索的點，這個時候棧里邊從top到他自己全是屬于該點為起點搜索的強連通分量。{cnt++;//強連通分量的個數do{x=Stack[top--];inStack[x]=0;}while(u!=x);//出棧最好模擬一下，出棧的循環中止條件為就是把那個u點彈出來為止}
}
int main()
{int x,y;while(scanf("%d%d",&n,&m)!=EOF,n+m){init();while(m--){scanf("%d%d",&x,&y);add(x,y);}for(int i=1;i<=n;i++)//從1開始進行縮點if(!dfn[i])tanjar(i);if(cnt==1)puts("Yes");elseputs("No");}
}

?

總結

以上是生活随笔為你收集整理的HDU - 1269迷宫城堡 -强连通tanjar算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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