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

佚名 6年前 (2019-05-06) 随笔 1537人围观抢沙发百度已收录

链接：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个欢迎关系，求被所有牛都欢迎的牛的数量。

思路：

强连通分量，缩点。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

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

就是在一个缩点后的图中，出度为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;
}