1 /* 2 題目大意：有N個cows, M個關系 3 a->b 表示 a認為b popular；如果還有b->c, 那么就會有a->c 4 問最終有多少個cows被其他所有cows認為是popular！ 5 6 思路：強連通分量中每兩個節點都是可達的！ 通過分解得到最后一個連通分量A， 7 如果將所有的強連通分量看成一個大的節點，那么A一定是孩子節點（因為我們先 8 完成的是父親節點的強連通分量）! 最后如果其他的強連通分量都可以指向A，那么 9 A中的每一個cow都會被其他cows所有的cows認為popular！ 10 */ 11 #include <string> 12 #include <cstdio> 13 #include <cstring> 14 #include <iostream> 15 #include<vector> 16 #define M 10005 17 using namespace std; 18 19 vector<int>ex[M]; 20 vector<int>ey[M]; 21 22 int n, m; 23 int cnt[M];//記錄第一次dfs的節點的逆序 24 int vis[M];//標記節點是否已經被訪問過了 25 int mark[M];//標記每一個節點是屬于哪一個連通分量 26 int ans; 27 int top; 28 29 void dfs1(int u){//出度遍歷 30 if(!vis[u]){ 31 vis[u]=1; 32 int len=ex[u].size(); 33 for(int i=0; i<len; ++i){ 34 int v=ex[u][i]; 35 dfs1(v); 36 } 37 cnt[top++]=u; 38 } 39 } 40 41 void dfs2(int u){//入度遍歷 42 if(!vis[u]){ 43 vis[u]=1; 44 mark[u]=ans; 45 int len=ey[u].size(); 46 for(int i=0; i<len; ++i){ 47 int v=ey[u][i]; 48 dfs2(v); 49 } 50 } 51 } 52 53 int main(){ 54 while(scanf("%d%d", &n, &m)!=EOF){ 55 while(m--){ 56 int u, v; 57 scanf("%d%d", &u, &v); 58 ex[u].push_back(v); 59 ey[v].push_back(u); 60 } 61 ans=top=0; 62 for(int i=1; i<=n; ++i) 63 if(!vis[i]) 64 dfs1(i); 65 66 memset(vis, 0, sizeof(vis)); 67 68 for(int i=top-1; i>=0; --i) 69 if(!vis[cnt[i]]){ 70 ++ans; 71 dfs2(cnt[i]); 72 } 73 int count=0; 74 int u=0; 75 for(int i=1; i<=n; ++i) 76 if(mark[i]==ans){ 77 ++count; 78 u=i; 79 } 80 memset(vis, 0, sizeof(vis)); 81 dfs2(u); 82 83 for(int i=1; i<=n; ++i)//其他的強連通分量是否都指向了最后一個強連通分量 84 if(!vis[i]){ 85 count=0; 86 break; 87 } 88 printf("%d\n", count); 89 for(int i=1; i<=n; ++i){ 90 ex[i].clear(); 91 ey[i].clear(); 92 } 93 memset(vis, 0, sizeof(vis)); 94 } 95 return 0; 96 }
1 /* 2 tarjan 算法果然nb！ 首先我們利用該算法將所有的強連通分量分開！ 3 然后將每一個連通分量看成是一個點，這樣就成了一個有向無環圖！ 4 接著判斷初度為 0 的點一共有多少個！如果只有一個，那么最終的答案就是 5 這個節點終所有子節點的個數！也就是說這個節點中的每一個子節點都能 6 其他的所有節點到達！ 7 8 如果初度為 0 的點多余1個，那么對不起，不能滿足某個節點恰好能被其他所有 9 的節點訪問到! 10 */#include<iostream> 11 #include<cstdio> 12 #include<vector> 13 #include<stack> 14 #include<cstring> 15 #define M 10005 16 using namespace std; 17 18 vector<int>edge[M]; 19 stack<int>s; 20 int low[M], vis[M]; 21 int sccN[M], pre[M]; 22 int n, m; 23 int dfs_clock, cnt; 24 25 void dfs(int u){//tarjan 算法 26 int len = edge[u].size(); 27 pre[u]=low[u]=++dfs_clock; 28 s.push(u); 29 for(int i=0; i<len; ++i){ 30 int v=edge[u][i]; 31 if(!pre[v]){ 32 dfs(v); 33 low[u]=min(low[u], low[v]); 34 } 35 else if(!sccN[v]) 36 low[u] = min(low[u], pre[v]); 37 } 38 if(low[u]==pre[u]){ 39 ++cnt; 40 while(1){ 41 int v=s.top(); 42 s.pop(); 43 sccN[v]=cnt; 44 if(u==v) break; 45 } 46 } 47 } 48 49 int main(){ 50 while(scanf("%d%d", &n, &m)!=EOF){ 51 dfs_clock=cnt=0; 52 memset(pre, 0, sizeof(pre)); 53 memset(sccN, 0, sizeof(sccN)); 54 memset(vis, 0, sizeof(vis)); 55 while(m--){ 56 int u, v; 57 scanf("%d%d", &u, &v); 58 edge[u].push_back(v); 59 } 60 for(int i=1; i<=n; ++i) 61 if(!pre[i]) 62 dfs(i); 63 int num=0; 64 for(int i=1; i<=n; ++i) 65 if(sccN[i]==1) 66 ++num; 67 int count=0; 68 memset(vis, 0, sizeof(vis)); 69 for(int i=1; i<=n; ++i){ 70 int len=edge[i].size(); 71 for(int j=0; j<len; ++j) 72 if(sccN[i] != sccN[edge[i][j]]){ 73 vis[sccN[i]]=1; 74 break; 75 } 76 } 77 78 for(int i=1; i<=cnt; ++i) 79 if(!vis[i]) ++count; 80 if(count==1) 81 printf("%d\n", num); 82 else printf("0\n"); 83 for(int i=1; i<=n; ++i) 84 edge[i].clear(); 85 while(!s.empty()) 86 s.pop(); 87 } 88 return 0; 89 } 1 /*比較慢的方法就是：利用tarjan算法將所有的強連通分量進行分離之后， 2 將每一個強連通分量看成是一個點，如果有滿足我們答案的解，那么初度為零 3 點一定只有一個，并且這個點的所有子節點的編號是 1！那么我們先計算出子節點 4 編號為 1的個數， 然后在判斷其他的強連通分量的節點是否能夠到達編號為 1 的 5 強連通分量！ */ 6 #include<iostream> 7 #include<cstdio> 8 #include<vector> 9 #include<stack> 10 #include<cstring> 11 #define M 10005 12 using namespace std; 13 14 vector<int>edge[M]; 15 stack<int>s; 16 int low[M], vis[M], used[M]; 17 int sccN[M], pre[M]; 18 int n, m; 19 int dfs_clock, cnt, sum, xx; 20 21 void dfs(int u){ 22 int len = edge[u].size(); 23 pre[u]=low[u]=++dfs_clock; 24 s.push(u); 25 for(int i=0; i<len; ++i){ 26 int v=edge[u][i]; 27 if(!pre[v]){ 28 dfs(v); 29 low[u]=min(low[u], low[v]); 30 } 31 else if(!sccN[v]) 32 low[u] = min(low[u], pre[v]); 33 } 34 if(low[u]==pre[u]){ 35 ++cnt; 36 while(1){ 37 int v=s.top(); 38 s.pop(); 39 sccN[v]=cnt; 40 if(u==v) break; 41 } 42 } 43 } 44 45 int dfs2(int u){ 46 int len=edge[u].size(); 47 if(sccN[u]==1){//到達之后就不在進行任何搜索 48 sum+=xx; 49 return 1; 50 } 51 vis[u]=1; 52 for(int i=0; i<len; ++i){ 53 int v=edge[u][i]; 54 if(!vis[v]){ 55 if(dfs2(v)) 56 return 1; 57 } 58 } 59 return 0; 60 } 61 62 int main(){ 63 while(scanf("%d%d", &n, &m)!=EOF){ 64 dfs_clock=cnt=0; 65 memset(pre, 0, sizeof(pre)); 66 memset(sccN, 0, sizeof(sccN)); 67 memset(vis, 0, sizeof(vis)); 68 memset(used, 0, sizeof(used)); 69 while(m--){ 70 int u, v; 71 scanf("%d%d", &u, &v); 72 edge[u].push_back(v); 73 } 74 for(int i=1; i<=n; ++i) 75 if(!pre[i]) 76 dfs(i); 77 int num=0; 78 sum=0; 79 used[1]=1; 80 for(int i=1; i<=n; ++i){ 81 82 if(sccN[i]==1) 83 ++num; 84 else if(!used[sccN[i]]){ 85 memset(vis, 0, sizeof(vis)); 86 xx=sccN[i]; 87 used[sccN[i]]=1; 88 dfs2(i); 89 } 90 } 91 92 if(sum==(cnt+1)*cnt/2-1)//最后將能到達標號為1的連通分量的所有強連通分量的標號加起來 93 printf("%d\n", num); 94 else printf("0\n"); 95 for(int i=1; i<=n; ++i) 96 edge[i].clear(); 97 while(!s.empty()) 98 s.pop(); 99 } 100 return 0; 101 }

?

?

?

轉載于:https://www.cnblogs.com/hujunzheng/p/3895221.html

總結

以上是生活随笔為你收集整理的poj2186Popular Cows（Kosaraju算法--有向图的强连通分量的分解）的全部內容，希望文章能夠幫你解決所遇到的問題。

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