受欢迎的牛

题目描述

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

输入格式

第一行两个数 $N,M$
接下来 $M$ 行，每行两个数 $A,B$ ，意思是 $A$ 认为 $B$ 是受欢迎的
(给出的信息有可能重复，即有可能出现多个 $A,B$ )。
$1\le N\le {10}^4,1\le M\le 5\times {10}^4$ 。

输出格式

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

输入

3 3
1 2  
2 1  
2 3  

输出

1

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

题解

受欢迎的奶牛只有可能是

• 图中唯一的出度为零的强连通分量中的所有奶牛，
  若出现两个以上出度为 0 的强连通分量

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

$\therefore$ 这时不存在明星奶牛

代码

#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';//输出该强连通分量的大小 
/*---------------核心代码--------------------*/
}