Problem Description

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

Input

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

Output

對于輸入的每組數(shù)據(jù)，如果任意兩個(gè)房間都是相互連接的，輸出”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

Author

Gardon

Source

HDU 2006-4 Programming Contest

Solution

• 這題是一道經(jīng)典的Tarjan題，直接求強(qiáng)連通分量！

• 如果整個(gè)圖的強(qiáng)連通分量的數(shù)量為1，那么說明這個(gè)圖是強(qiáng)連通的。

Code

#include<cstdio> #include<cstring> #define P(x) putchar(x) using namespace std; const int N=10001; int tot,now,top,num,n,m; int first[N],next[N*10],en[N*10]; int dfn[N],low[N],stack[N]; bool bz[N]; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; } inline void tarjan(int x) {if(num>1) return;dfn[x]=low[x]=++now;bz[stack[++top]=x]=true;for(int i=first[x];i;i=next[i])if(!dfn[en[i]]){tarjan(en[i]);if(low[en[i]]<low[x]) low[x]=low[en[i]];}elseif(bz[en[i]] && dfn[en[i]]<low[x]) low[x]=dfn[en[i]];if(dfn[x]==low[x]){do{bz[stack[top--]]=false;}while(stack[top+1]!=x);num++;} } int main() {while(true){n=read(),m=read();if(!n && !m) return 0;memset(first,0,sizeof(first));memset(dfn,0,sizeof(dfn));now=tot=top=num=0;for(int i=1;i<=m;i++){int x=read(),y=read();next[++tot]=first[x];first[x]=tot;en[tot]=y;}for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);if(num==1) P('Y'),P('e'),P('s'); else P('N'),P('o');P('\n');} }

總結(jié)

以上是生活随笔為你收集整理的Hdu 1269.迷宫城堡的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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