POJ 2186 Popular Cows(强连通分量缩点)

题目意思大概是：给定N（N<=10000)个点和M（M<=50000)条有向边，求有多少个“受欢迎的点”。所谓的“受欢迎的点”当且仅当任何一个点出发都能到达它。

原来的图是无序且可能有环，用tarjan缩点，变成一个DAG。受欢迎点的出度一定为0，所以缩点后求有多少个连通分量的出度是0，要是大于1则没有受欢迎的点，等于1的话求出这个出度为0的连通分量有多少个点。

强联通分量tarjan算法里邻接表用vector一般好理解，但是速度不及链式前向星，链式前向星学习链接：http://blog.csdn.net/acdreamers/article/details/16902023

AC代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int MAXN = 1e4 + ;

 struct data {

     int next , to;

 }edge[MAXN * ];

 int head[MAXN] , low[MAXN] , dfn[MAXN] , block[MAXN] , st[MAXN];

 int top , ord , sccnum;

 bool instack[MAXN] , out[MAXN];

 void init(int n) {

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

         low[i] = dfn[i] = ;

         head[i] = -;

         instack[i] = false;

     }

     top = ord = sccnum = ;

 }

 void tarjan(int u) {

     low[u] = dfn[u] = ++ord;

     st[++top] = u;

     instack[u] = true;

     for(int i = head[u] ; ~i ; i = edge[i].next) { //链式前向星

         int v = edge[i].to;

         if(!dfn[v]) {

             tarjan(v);

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

         }

         else if(instack[v]) {

             low[u] = min(low[u] , dfn[v]);

         }

     }

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

         int v;

         sccnum++;

         do {

             v = st[top--];

             instack[v] = false;

             block[v] = sccnum;

         }while(u != v);

     }

 }

 int main()

 {

     int n , m , u , v;

     while(~scanf("%d %d" , &n , &m)) {

         init(n);

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

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

             edge[i].to = v;     //链式前向星

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

             head[u] = i;

         }

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

             if(!dfn[i])

                 tarjan(i);

         }

         memset(out , false , sizeof(out)); //缩点是否有入度

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

             for(int i = head[u] ; ~i ; i = edge[i].next) { //链式前向星

                 int v = edge[i].to;

                 if(block[v] != block[u])  //不是同一个连通分量

                     out[block[u]] = true;

             }

         }

         int res =  , op = -;

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

             if(!out[i]) {  //出度为0的点

                 res++;

                 op = i;

             }

         }

         if(res > ) {

             printf("0\n");

         }

         else {

             res = ;

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

                 if(block[i] == op)

                     res++;

             }

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

         }

     }

 }

巴特西

POJ 2186 Popular Cows(强连通分量缩点)

最新文章

热门文章