洛谷题单指南-连通性问题-P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

原题链接：https://www.luogu.com.cn/problem/P2341

题意解读：把奶牛看作图中节点，奶牛的喜欢关系看作有向边，求有多少节点可以被所有节点走到。

解题思路：

如果是一个DAG，问题就好办了，能被所有节点走到的节点就是出度为0的那个节点，如果有多个出度为0的节点，则不能互相走到。

但是不是DAG，就要想办法变成DAG，通过对强联通分量缩点，即可得到DAG。

判断出度为0的缩点个数，大于1则答案为0，否则输出出度为0的缩点中节点的个数，即为答案。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 10005, M = 50005;
int head[N], to[M], nxt[M], idx;
int dfn[N], low[N], timestamp;
stack<int> stk;
bool vis[N];
int cnt;
int scc[N], sz[N], out[N];
int n, m;

void add(int a, int b)
{
    to[++idx] = b;
    nxt[idx] = head[a];
    head[a] = idx;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    vis[u] = true;
    for(int i = head[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        cnt++;
        while(true)
        {
            int v = stk.top();
            stk.pop();
            vis[v] = false;
            scc[v] = cnt;
            sz[cnt]++;
            if(v == u) break;
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i);

    //统计每个强连通分量的出度
    for(int u = 1; u <= n; u++)
    {
        for(int j = head[u]; j; j = nxt[j])
        {
            int v = to[j];
            if(scc[u] != scc[v]) out[scc[u]]++;
        }
    }

    int ans = 0, sum = 0;
    for(int i = 1; i <= cnt; i++)
    {
        if(out[i] == 0) sum++, ans += sz[i];
    }
    if(sum > 1) cout << 0 << endl;
    else cout << ans << endl;
    return 0;
}