poj 2186 强连通入门题目

每头牛的梦想就是成为牛群中最受欢迎的牛。在一群N（1 <= N <= 10,000）母牛中，

你可以得到M（1 <= M <= 50,000）有序的形式对（A，B），告诉你母牛A认为母牛 B很受欢迎。

由于流行是传递性的，如果A认为B很受欢迎，B认为C受欢迎，那么A也会认为C是
流行的，即使这不是输入中有序对明确规定的。

你的任务是计算每头奶牛认为受欢迎的奶牛数量。

水题强连通入门题目。

tarjin缩点然后就变成一棵树，

然后就是求有多少个点的出度为0

输入这个点里面包含的所有点，因为有缩点出来的

所有输出他的强连通分量

缩点后如果有多个出度为0的点，这样是不符合题意的，输出0

不联通也是输出0

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int maxn = 1e5 + ;

 int n, m, u, v, tot, top, cnt, flag;

 struct node {

     int v, next;

 } edge[maxn];

 int head[maxn], instack[maxn], s[maxn];

 int dfn[maxn], low[maxn], belong[maxn];

 void init() {

     tot = cnt = top = flag = ;

     memset(head, -, sizeof(head));

     memset(dfn, , sizeof(dfn));

     memset(instack, , sizeof(instack));

 }

 void add(int u, int v) {

     edge[tot].v = v;

     edge[tot].next = head[u];

     head[u] = tot++;

 }

 void tarjin(int v) {

     dfn[v] = low[v] = ++flag;

     instack[v] = ;

     s[top++] = v;

     for (int i = head[v] ; i != - ; i = edge[i].next) {

         int j = edge[i].v;

         if (!dfn[j]) {

             tarjin(j);

             low[v] = min(low[v], low[j]);

         } else if (instack[j]) low[v] = min(low[v], dfn[j]);

     }

     if (dfn[v] == low[v]) {

         cnt++;

         int t;

         do {

             t = s[--top];

             instack[t] = ;

             belong[t] = cnt;

         } while(t != v) ;

     }

 }

 int du[maxn];

 void solve() {

     for (int i =  ; i <= n ; i++)

         if (!dfn[i]) tarjin(i);

 }

 int main() {

     while(scanf("%d%d", &n, &m) != EOF) {

         if (n ==  && m == ) break;

         init();

         memset(du, , sizeof(du));

         for (int i =  ; i < m ; i++) {

             scanf("%d%d", &u, &v);

             add(u, v);

         }

         for (int i =   ; i <= n ; i++)

             if (!dfn[i]) tarjin(i);

         for (int i =  ; i <= n ; i++) {

             for (int j = head[i] ; ~j; j = edge[j].next ) {

                 if (belong[edge[j].v] != belong[i]) du[belong[i]]++;

             }

         }

         int ansrt, zero = ;

         for (int i =  ; i <= cnt ; i++) {

             if (!du[i]) {

                 ansrt = i;

                 zero++;

             }

         }

         if (zero == ) {

             int ans = ;

             for (int i =  ; i <= n ; i++) {

                 if (belong[i] == ansrt) ans++;

             }

             printf("%d\n", ans);

         } else printf("0\n");

     }

     return ;

 }

巴特西

poj 2186 强连通入门题目

最新文章

热门文章