hdu1269 移动城堡联通分量 Tarjan

思路：tarjan求强连通分量判断ans==n?

卿学姐视频：http://www.bilibili.com/video/av7330663/

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int INF = 1<<30;
 5 const int maxn = 1e4+7;
 6 
 7 int dfn[maxn],low[maxn],vis[maxn],tot,n,m,ans;
 8 vector<int> E[maxn];
 9 stack<int> S;
10 
11 void tarjan(int x){
12     low[x] = dfn[x] = ++tot;
13     S.push(x);
14     vis[x] = 1;
15 
16     for(int i=0; i<E[x].size(); i++){
17         int v = E[x][i];
18 
19         if(!dfn[v]){
20             tarjan(v);
21             low[x] = min(low[x],low[v]);
22         }else if(vis[v]){
23             low[x] = min(low[x],dfn[v]);
24         }
25     }
26 
27     if(low[x] == dfn[x]){
28         int cnt = 0;
29         while(1){
30             int now = S.top();
31             S.pop();
32             vis[x] = 0;
33             cnt++;
34             if(now == x) break;
35         }
36 
37         if(cnt >= 1) ans = min(ans,cnt);
38     }
39 }
40 
41 int main(){
42     
43     while(scanf("%d%d",&n,&m)==2 && (n||m)){
44         memset(dfn,0,sizeof(dfn));
45         memset(low,0,sizeof(low));
46         memset(vis,0,sizeof(vis));
47 
48         ans = INF;
49         tot = 0;
50         while(!S.empty()) S.pop();
51         for(int i=0; i<maxn; i++) E[i].clear();
52 
53         for(int i=1; i<=m; i++){
54             int u,v;
55             scanf("%d%d",&u,&v);
56             E[u].push_back(v);
57         }
58     
59         for(int i=1; i<=n; i++){
60             if(!dfn[i])
61                 tarjan(i);
62         }
63     
64         cout << ((ans==n)?"Yes":"No") << endl;
65     }
66 
67 }

hdu1269 移动城堡 联通分量 Tarjan

hdu1269 移动城堡联通分量 Tarjan