題意：
? ? ? 有一群老牛，給你一些關系，a b表示牛a仰慕牛b，最后問你有多少個牛是被所有牛仰慕的。

思路：

? ? ? 假如這些仰慕關系不會出現(xiàn)環(huán)，那么當且僅當只有一只牛的出度為0的時候答案才是1，都則就是0，再假設所有的關系正好組成了一個環(huán)，那么就是說明每只牛都沒其他所有牛仰慕，那么答案就是n，所以我們可以像強聯(lián)通縮點之后看是否有且僅有一個出度為0的，如果有那么答案就是那個強聯(lián)通分量的元素個數(shù)，否則就是0，因為同一個強聯(lián)通里面的點有著相同的性質.

#include<stdio.h> #include<string.h> #include<stack>#define N_node 10000 + 100 #define N_edge 50000 + 500using namespace std;typedef struct {int to ,next; }STAR;typedef struct {int a ,b; }EDGE;STAR E1[N_edge] ,E2[N_edge]; EDGE edge[N_edge]; int list1[N_node] ,list2[N_node] ,tot; int Belong[N_node] ,cont; int out[N_node] ,sum[N_node]; int mark[N_node]; stack<int>st;void add(int a ,int b) {E1[++tot].to = b;E1[tot].next = list1[a];list1[a] = tot;E2[tot].to = a;E2[tot].next = list2[b];list2[b] = tot; }void DFS1(int s) {mark[s] = 1;for(int k = list1[s] ;k ;k = E1[k].next){int to = E1[k].to;if(!mark[to])DFS1(to);}st.push(s); }void DFS2(int s) {Belong[s] = cont;sum[cont] ++;mark[s] = 1;for(int k = list2[s] ;k ;k = E2[k].next){int to = E2[k].to;if(!mark[to]) DFS2(to);} }int main () {int n ,m ,a ,b ,i;while(~scanf("%d %d" ,&n ,&m)){memset(list1 ,0 ,sizeof(list1));memset(list2 ,0 ,sizeof(list2));tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d %d" ,&a ,&b);add(a ,b);edge[i].a = a;edge[i].b = b;}while(!st.empty())st.pop();memset(mark ,0 ,sizeof(mark));for(i = 1 ;i <= n ;i ++)if(!mark[i])DFS1(i); cont = 0;memset(mark ,0 ,sizeof(mark));memset(sum ,0 ,sizeof(sum));while(!st.empty()){int to = st.top();st.pop();if(!mark[to]){cont ++;DFS2(to);}}memset(out ,0 ,sizeof(out));for(i = 1 ;i <= m ;i ++){a = Belong[edge[i].a];b = Belong[edge[i].b];if(a == b) continue;out[a] ++;}int ss = 0 ,mk = -1;for(i = 1 ;i <= cont ;i ++){if(!out[i]){ss ++;mk = i;}}if(ss == 1) printf("%d\n" ,sum[mk]);else printf("0\n");}return 0; }

總結

以上是生活随笔為你收集整理的POJ2186 强联通的全部內容，希望文章能夠幫你解決所遇到的問題。

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