HDU1269 迷宮城堡

文章目錄

• • Problem Description
  • 題解：

Problem Description

為了訓練小希的方向感，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

題解：

問這個圖是不是只有一個強連通圖。
tarjan求強連通分量的模板題
建議背誦
tarjan不清楚的可以看我另一個博客詳細的講解
鏈式前項星版

#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]; void init() {top=tot = cnt = 0;memset(head,-1,sizeof head);memset(vis,0,sizeof vis);for(int i = 1; i<=n; i++) dfn[i] = low[i] = 0; } 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;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++;} int main() {int a,b;while(~scanf("%d%d",&n,&m)) {if(n == 0 && m == 0) break;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 ; }

二維矩陣版

#include<bits/stdc++.h> #define mem(a) memset(a,0,sizeof(a)) using namespace std; int n,m; const int maxn=100004; int low[maxn],dfn[maxn]; int vis[maxn]; vector<int>mp[maxn]; int cnt=0; int sign; void init() {mem(low);mem(dfn);mem(vis);mem(mp);cnt=0;sign=0;} void Tarjan(int u) {vis[u]=1;low[u]=dfn[u]=++cnt;for(int i=0;i<mp[u].size();i++){int v=mp[u][i];if(dfn[v]==0){Tarjan(v);low[u]=min(low[u],low[v]);}else if(vis[v]==1)low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u])sign++; } int main() {while(cin>>n>>m){if(n==0&&m==0)break;init();for(int i=1;i<=m;i++){ int x,y;cin>>x>>y;mp[x].push_back(y);}for(int i=1;i<=n;i++){if(dfn[i]==0)Tarjan(i);}if(sign!=1)cout<<"No"<<endl;else cout<<"Yes"<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的HDU1269 迷宫城堡（模板题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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