題意：
? ? ? 有一群老牛，他們之間有m組敬仰關系，關系可以傳遞，a仰慕b，b仰慕c，那么a就仰慕c,現在問被所有老牛都仰慕
的有多少？


思路：

? ? ? 想想，是不是一個環中的老牛的關系都是一樣的，就是只要有一只牛仰慕了環里面的任何一只牛，那么這個環里的所有牛都將被這只牛仰慕，那好，我們進行強聯通縮點，然后出度為0的那個連通快就是被所有牛都仰慕的。前提是出度為0的連通快只能有一個才行，否則就輸出0.

#include<stack> #include<stdio.h> #include<string.h>#define N_node 10000 + 100 #define N_edge 50000 + 500using namespace std;typedef struct {int to ,next; }STAR;typedef struct {int a ,b; }EDGE;EDGE edge[N_edge]; STAR E1[N_edge] ,E2[N_edge]; stack<int>sk; int mark[N_node]; int list1[N_node] ,list2[N_node] ,tot; int Belong[N_node] ,Cnt; int Cout[N_node];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)if(!mark[E1[k].to])DFS1(E1[k].to);sk.push(s); }void DFS2(int s) {mark[s] = 1;Belong[s] = Cnt;for(int k = list2[s] ;k ;k = E2[k].next)if(!mark[E2[k].to]) DFS2(E2[k].to); }int solve(int n ,int m) {memset(mark ,0 ,sizeof(mark));while(!sk.empty()) sk.pop();for(int i = 1 ;i <= n ;i ++)if(!mark[i]) DFS1(i);Cnt = 0;memset(mark ,0 ,sizeof(mark));while(!sk.empty()){int xin = sk.top();sk.pop();if(mark[xin]) continue;++Cnt;DFS2(xin);}memset(Cout ,0 ,sizeof(Cout));for(int i = 1 ;i <= m ;i ++){int a = Belong[edge[i].a];int b = Belong[edge[i].b];if(a==b)continue;Cout[a] ++;}int s = 0;for(int i = 1 ;i <= Cnt ;i ++)if(!Cout[i]) s ++;if(s != 1) return 0;s = 0;for(int i = 1 ;i <= n ;i ++)if(!Cout[Belong[i]]) s ++;return s; }int main () {int n ,m ,i ,a ,b;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;}printf("%d\n" ,solve(n ,m));}return 0; }

總結

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

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