Popular Cows(Targin + 缩点)

向右看齐 2021-12-12 10:17 226阅读 0赞

题目链接:poj.org/problem?id=2186

分析：  
根据题意我们要求的是这样的结点的个数（即：除本结点以外的其他结点都能到达这个结点 就是其他结点都能有路径到这个结点）。如果我们暴力，那肯定gg。 所以，我们在想，可以用强联通进行缩点，即一个强联通分量中的每任意两个结点是可以相互到达的。  
所以可以把一个强联通分量看成一个点。这样在点数上就少很多了并且是成了一个有向的树。继续考虑，在这个树上，我们要求的是一个其他结点都能到达这个结点的结点。所以故所求结点的出度一定为0。并且在这个树中，一定只有一个出度为0的点。因为当有两个以上的时候，则此两个结点一定是互不相连的。那么当出度为0的结点有两个以上，则答案是0。

如何缩点呢？  
这个根据每个结点的染色值进行缩点。相同颜色的值为一个强联通分量。

在建树的时候，可以根据颜色值进行建树，这样会方便一些。

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    
    int N,M;
    vector<int> Q[10010];
    int color[10010],vis[10010],dfn[10010],low[10010],Stack[10010],in[10010],visit[10010];
    int out[10010];
    int color_num[10010];
    int col_num,dfn_num,cnt,top;
    
    void Targin(int x)
    {
        dfn[x] = ++ dfn_num;
        low[x] = dfn_num;
        Stack[++ top] = x;
        vis[x] = 1;
        for(int i = 0; i < Q[x].size(); i ++)
        {
            int v = Q[x][i];
            if(!dfn[v])
            {
                Targin(v);
                low[x] = min(low[x],low[v]);
            }
            else
                if(vis[v])
                {
                   low[x] = min(low[x],dfn[v]);
                }
        }
        if(low[x] == dfn[x])
        {
            color[x] = ++ col_num;
            color_num[col_num] ++;
            vis[x] = 0;
            while(Stack[top] != x)
            {
                color[Stack[top]] =  col_num;
                color_num[col_num] ++;
                vis[Stack[top --]] = 0;
            }
            top --;
        }
    }
    
    int main()
    {
        scanf("%d%d",&N,&M);
        for(int i = 1; i <= M; i ++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            Q[a].push_back(b);
        }
        for(int i = 1; i <= N;i ++)
        {
            if(!dfn[i])
                Targin(i);
        }
        //for(int i = 1; i <= N; i ++)
        //    printf("%d = %d\n",i,color[i]);
        for(int i = 1; i <= N;i ++) //缩点
        {
           for(int j = 0; j < Q[i].size(); j ++)
           {
               int v = Q[i][j];
               if(color[i] !=  color[v])
               {
               //表color[v] 和 color[i] 这两个颜色值 分别有一个入度和出度
                   in[color[v]] ++; out[color[i]] ++;
               }
           }
        }
        int num = 0;
        int number = 0;
        for(int i = 1; i <= col_num; i ++)
            if(out[i] == 0)
               {
                   num ++;
                   number = color_num[i];
               }
        //printf("num = %d\n",num);
        if(num == 1)
            printf("%d\n",number);
        else
            printf("0\n");
    }