POJ-2186-Popular Cows（强连通分量，缩点）

Dear 丶 2021-12-23 11:34 204阅读 0赞

### 链接：[https://vjudge.net/problem/POJ-2186][https_vjudge.net_problem_POJ-2186] ###

### 题意： ###

有N(N<=10000)头牛，每头牛都想成为most poluler的牛，给出M(M<=50000)个关系，如(1,2)代表1欢迎2，关系可以传递，但是不可以相互，即1欢迎2不代表2欢迎1，但是如果2也欢迎3那么1也欢迎3.  
给出N,M和M个欢迎关系，求被所有牛都欢迎的牛的数量。

### 思路： ###

强连通分量， 缩点。

先求出强连通分量，在根据缩点建立新图。

缩点：即在原图上，将一个强连通子图给看成一个点来处理，本题被所有牛都欢迎的牛，

就是在一个缩点后的图中，出度为0的点，点中的所有牛都是满足条件的牛。

如果出度为0的点大于1，则没有一个牛满足条件。

### 代码： ###

#include <iostream>
    #include <memory.h>
    #include <cstdio>
    #include <map>
    #include <string>
    #include <cstring>
    #include <vector>
    #include <set>
    #include <stack>
    #include <algorithm>
    using namespace std;
    typedef long long LL;
    
    const int MAXN = 1e4+10;
    
    vector<int> G[MAXN];
    stack<int> St;
    int Dfn[MAXN], Low[MAXN];
    int Fa[MAXN], Vis[MAXN];
    int Dis[MAXN];
    int n, m;
    int sum, times;
    int cnt;
    
    void Tarjan(int x)
    {
        St.push(x);
        Vis[x] = 1;
        Dfn[x] = Low[x] = ++times;
        for (int i = 0;i < G[x].size();i++)
        {
            int node = G[x][i];
            if (Dfn[node] == 0)
            {
                Tarjan(node);
                Low[x] = min(Low[x], Low[node]);
            }
            else if (Vis[node] == 1)
            {
                Low[x] = min(Low[x], Dfn[node]);
            }
        }
        if (Dfn[x] == Low[x])
        {
            cnt++;
            while (St.top() != x)
            {
                Fa[St.top()] = cnt;
                Vis[St.top()] = 0;
                St.pop();
            }
            Fa[St.top()] = cnt;
            Vis[St.top()] = 0;
            St.pop();
        }
    }
    
    void Init()
    {
        for (int i = 1;i <= n;i++)
            G[i].clear(), Fa[i] = i;
        while (St.size())
            St.pop();
        memset(Dfn, 0, sizeof(Dfn));
        memset(Low, 0, sizeof(Low));
        memset(Vis, 0, sizeof(Vis));
        memset(Dis, 0, sizeof(Dis));
        cnt = times = 0;
    }
    
    int main()
    {
        while (cin >> n >> m)
        {
            int l, r;
            for (int i = 1;i <= m;i++)
            {
                cin >> l >> r;
                G[l].push_back(r);
            }
            for (int i = 1;i <= n;i++)
                if (Dfn[i] == 0)
                    Tarjan(i);
            for (int i = 1;i <= n;i++)
            {
                for (int j = 0;j < G[i].size();j++)
                {
                    int node = G[i][j];
                    if (Fa[i] != Fa[node])
                        Dis[Fa[i]]++;
                }
            }
            int ans = 0, u;
            for (int i = 1;i <= cnt;i++)
                if (Dis[i] == 0)
                    ans++, u = i;
            if (ans == 1)
            {
                int res = 0;
                for (int i = 1;i <= n;i++)
                    if (Fa[i] == u)
                        res++;
                cout << res << endl;
            }
            else
                cout << 0 << endl;
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/YDDDD/p/10820463.html

[https_vjudge.net_problem_POJ-2186]: https://vjudge.net/problem/POJ-2186