POJ2186 强联通

题意：

有一群老牛，给你一些关系，a b表示牛a仰慕牛b，最后问你有多少个牛是被所有牛仰慕的。

思路：

假如这些仰慕关系不会出现环，那么当且仅当只有一只牛的出度为0的时候答案才是1，都则就是0，再假设所有的关系正好组成了一个环，那么就是说明每只牛都没其他所有牛仰慕，那么答案就是n，所以我们可以像强联通缩点之后看是否有且仅有一个出度为0的，如果有那么答案就是那个强联通分量的元素个数，否则就是0，因为同一个强联通里面的点有着相同的性质.

#include<stdio.h>

#include<string.h>

#include<stack>

#define N_node 10000 + 100

#define N_edge 50000 + 500

using 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 强联通

最新文章

热门文章