poj 2186_Popular Cows_强连通分量

发布于 2019-05-23  18 次阅读


题目大意

n头奶牛,给出若干个欢迎关系a b,表示a欢迎b,欢迎关系是单向的,但是是可以传递的。另外每个奶牛都是欢迎他自己的。求出被所有的奶牛欢迎的奶牛的数目

思路

用tarjan求出强连通分量
如果有多个出度为0的强连通分量的话那么就是无解的,因为肯定有两头牛不互相喜欢
如果只有一个强连通分量,那么全部牛都是popular cows
如果只有一个出度为0的强连通分量,那么求出这个强连通分量中的点的个数就是答案
#include 
#include 
#include 
#include 
using namespace std;
#define maxn 10001
#define maxm 50005
#define fill(x, y) memset(x, y, sizeof(y))
int bcnt = 0, dindex = 0;
int ls[maxm], dfn[maxn], low[maxn], belong[maxn], in[maxn], out[maxn]; 
bool instack[maxn];
int n, m;
struct edge
{
    int from, to ,next;
}e[maxm];
stack s;
int tarjan(int x)
{
    dindex++;
    dfn[x] = dindex;
    low[x] = dindex;
    s.push(x);
    instack[x] = 1;
    for (int i = ls[x]; i; i = e[i].next)
    {
        int to = e[i].to;
        if (dfn[to] == 0)
        {
            tarjan(to);
            if (low[x] > low[to]) low[x] = low[to];
        }
        else
        {
            if (instack[to] && dfn[to] < low[x]) 
                low[x] = dfn[to];
        }
    }
    if (low[x] == dfn[x])
    {
        bcnt++;
        int j;
        do
        {
            j = s.top();
            s.pop();
            instack[j] = 0;
            belong[j] = bcnt;
        }
        while (x != j);
    }
    return 0;
}
int solve()
{
    while (! s.empty()) s.pop();
    fill(dfn, 0);
    for (int i = 1; i <= n; i++)
        if (dfn[i] == 0) tarjan(i);
    return 0;
}
int main()
{
    while(~scanf("%d%d", &n, &m))
    {
            int l = 0;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        e[++l].from = x;
        e[l].to = y;
        e[l].next = ls[x];
        ls[x] = l;
    }
    solve();
    if (bcnt == 1) 
    {
        printf("%d\n", n);
        continue;
    }
    for (int i = 1; i <= m; i++)
    {
        if (belong[e[i].from] != belong[e[i].to])
        {
            out[belong[e[i].from]]++;
            in[belong[e[i].to]]++;
        }
    }
    int ans = 0, u = 0;
    for (int i = 1; i <= bcnt; i++)
    {
        if (out[i] == 0) 
        {
            ans++;
            u = i;
        }
    }
    if (ans > 1) printf("%d\n", 0);
    else
    {
        int an = 0;
        for (int i = 1; i <= n; i++)
            if (belong[i] == u) an++;
        printf("%d\n", an);
    }
    }
}
]]>