受欢迎的牛

题目描述

原题来自：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 \leq N \leq 10^{4}, 1 \leq M \leq 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';//输出该强连通分量的大小 
/*---------------核心代码--------------------*/
}