受欢迎的牛

题目描述

原题来自:USACO 2003 Fall
每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛,给你 M 对整数 (A,B) ,表示牛 A 认为牛 B 受欢迎。这种关系是具有传递性的,如果 A 认为 B 受欢迎, B 认为 C 受欢迎,那么牛 A 也认为牛 C 受欢迎。你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。

输入格式

第一行两个数 N,M
接下来 M 行,每行两个数 A,B ,意思是 A 认为 B 是受欢迎的
(给出的信息有可能重复,即有可能出现多个 A,B )。
1N104,1M5×104

输出格式

输出被除自己之外的所有牛认为是受欢迎的牛的数量。

输入

3 3
1 2  
2 1  
2 3  

输出

1

Notes:只有第三头牛被除自己之外的所有牛认为是受欢迎的。

题解

受欢迎的奶牛只有可能是

这时已经有两个奶牛不喜欢任何人了,就不可能存在明星奶牛了。

这时不存在明星奶牛

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m, dfn[N], low[N], instk[N], siz[N], top, tot, cnt, scc[N], stk[N], cdu[N];
vector<int> e[N];
void tarjan(int x)
{
    dfn[x] = low[x] = ++tot;
    stk[++top] = x;
    instk[x] = 1;

    for (int y : e[x])
    { //邻接表存图
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (instk[y])
        {
            low[x] = min(low[x], low[y]);
        }
    }

    if (dfn[x] == low[x])
    {
        int y;
        ++cnt;
        do
        {
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt;
            ++siz[cnt];
        } while (y != x);
    }
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
            tarjan(i);
    }
/*---------------核心代码--------------------*/
    //记录强连通分量的出度
    for (int x = 1; x <= n; x++)
        for (int y : e[x])
            if (scc[x] != scc[y])
                cdu[scc[x]]++;//rdu[scc[y]]++;
    int ans = 0;
    for (int i = 1; i <= cnt; i++)
    {
        if(!cdu[i])
        {
            if(ans)
            {
                cout << 0 << '\n';//出现两个以上出度为 0 的强连通分量
                return 0;
            }
            ans = i;
        }
    }
    cout << siz[ans] << '\n';//输出该强连通分量的大小 
/*---------------核心代码--------------------*/
}