poj 2186 Popular Cows 【强连通】

矫情吗；* 2022-08-13 15:46 4阅读 0赞

题目：[poj 2186 Popular Cows][]

题意：n头牛，其中存在一些牛相互崇拜，具有传递性，问有多少头牛是被其他所有牛崇拜的。

分析：建立一个有向图，然后强连通缩点，之后求出度为0的点，假如存在多个，那么ans = 0，因为缩点之后如果x崇拜y，x也崇拜z，那么肯定y和z不能互相崇拜，不满足。

然后求出度为0的这个点缩点前环上有多少个点就ans

AC代码：

#include <cstdio>
    #include <vector>
    #include <iostream>
    #include <stack>
    #include <cstring>
    using namespace std;
    const int N = 25000;
    vector<int> G[N];
    int pre[N],lowlink[N],sccno[N],dfs_clock,scc_cnt; //sccno【i】 i所在的scc图的编号
    //scc_cnt 联通块的数量
    stack<int> s;
    
    void dfs(int u)
    {
        pre[u] = lowlink[u] = ++dfs_clock;
        s.push(u);
        for(int i=0; i<G[u].size(); i++)
        {
            int v=G[u][i];
            if(!pre[v])
            {
                dfs(v);
                lowlink[u]=min(lowlink[u],lowlink[v]);
            }
            else if(!sccno[v])
            {
                lowlink[u]=min(lowlink[u],pre[v]);
            }
        }
        if(lowlink[u]==pre[u])
        {
            scc_cnt++;
            for(;;)
            {
                int x=s.top();
                s.pop();
                sccno[x]=scc_cnt;
                if(x==u)
                    break;
            }
        }
    }
    void find_scc(int n)
    {
        dfs_clock=scc_cnt=0;
        memset(sccno,0,sizeof(sccno));
        memset(pre,0,sizeof(pre));
        for(int i=0; i<n; i++)
            if(!pre[i]) dfs(i);
    }
    int in[N],out[N];
    void workout(int n) {
        memset(out,0,sizeof(out));
        for (int u = 0; u < n; u++) {
            for (int i = 0; i < G[u].size(); i++) {
                int v = G[u][i];
                //printf("%d %d %d %d\n",u+1,v+1,sccno[u],sccno[v]);
                if (sccno[u] != sccno[v]) {
                    out[sccno[u]] += 1;
                }
            }
        }
        int pps = 0,ans = 0,sum = 0;
        for(int i=1;i<=scc_cnt;i++) {
            if (out[i] == 0){
                sum++;
                pps = i;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(sccno[i]==pps)
                ans++;
        }
        if(sum==1)
            printf("%d\n",ans);
        else
            puts("0");
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n,m,T;
        while(~scanf("%d",&n))
        {
            scanf("%d",&m);
            for(int i=0;i<m;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                G[x-1].push_back(y-1);
            }
            find_scc(n);
            workout(n);
            for(int i=0;i<n;i++)
                G[i].clear();
        }
        return 0;
    }

[poj 2186 Popular Cows]: http://poj.org/problem?id=2186