LOJ 10091 受欢迎的牛（SCC + 缩点）

题意

有 n 头牛、m 条「A 认可 B」的有向关系，认可可以传递（A 认可 B、B 认可 C ⇒ A 认可 C）。 问被所有牛认可的牛有多少头；若不存在则输出 0。

思路（我的写法）

这道题可以发现近似于是一个缩点模板的题，首先使用tarjan找出强连通分量，然后通过数组scc 把这些分量连接，这是缩点。后面发现如果一个奶牛有其他n-1个奶牛认可，那么可以通过dfs累加sz 这样就可以通过判断sz[i]是否等于n来决定ans++。注意的是,tarjan算出来的scc是反着来的， 所以加上一些细节便可以实现本题目。

展开成三步：

1. 缩点：同一个 SCC 里的牛互相认可，所以它们的答案必然相同 → 一个 SCC 压成一个点，点权就是分量大小 sz。
2. 建反图：原图边 cu → cv 表示「cu 的牛认可 cv 的牛」。我们关心的是「有哪些牛能到达 i」，于是把边反向存成 cv → cu，从 i 出发 DFS 能走到谁，就是「谁能认可 i」。
3. 统计：dfs(i) 把沿途所有分量的点权累加起来，得到「能认可 i 的牛数」；等于 n 就说明所有牛都认可 i，答案加上这个分量的大小。

关键细节：Tarjan 弹栈得到的分量编号是逆拓扑序（先出栈的是拓扑序靠后的），所以建反图、遍历时直接用编号区间 1..sc 即可，不需要再跑一遍拓扑排序。

复杂度

• 时间：O(n + m) —— Tarjan 一遍 DFS；缩点后每个分量只被 DFS 算一次（vis 记忆化）。
• 空间：O(n + m)。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
static const long long MOD = 998244353;
const int N = 1e4+10;
vector<int> g[N];
int df[N],low[N],inst[N],tot;
//stack<int> st;
int id,sz[N],scc[N],sc,s[N];

void tarjan(int u){
    df[u]=low[u]=++tot;
    inst[u]=1;
    s[++id]=u;
    for(auto v:g[u]){
        if(!df[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(inst[v]){
            low[u]=min(low[u],df[v]);
        }
    }
    if(df[u]==low[u]){
        ++sc;
        do{
            scc[s[id]]=sc;
            sz[sc]++;
            inst[s[id]]=0;
        }while(s[id--]!=u);
    }
}
int n,m;
vector<int> e[N];
int a[N];
int vis[N];
int dfs(int u){
    if(vis[u]) return sz[u];
    vis[u]=1;
    for(auto v:e[u]){
        dfs(v);
        sz[u]+=sz[v];
    }
    return sz[u];
}
void sol() {
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        g[a].push_back(b);
    }    
    for(int i=1;i<=sc;i++){
        sort(g[i].begin(),g[i].end());
        g[i].erase(unique(g[i].begin(),g[i].end()),g[i].end());
    }
    for(int i=1;i<=n;i++) if(!df[i]) tarjan(i);
    for(int u=1;u<=n;u++){
        for(auto v:g[u]){
            int cu=scc[u],cv=scc[v];
            //cout<<cu<<" "<<cv<<endl;
            if(cu!=cv) e[cv].push_back(cu);
        }
    }
    vector<int> a(sc+1,0);
    for(int i=1;i<=sc;i++) a[i]=sz[i];
    for(int i=1;i<=sc;i++){
        //for(auto v:e[i]) cout<<v<<" "<<i<<endl;
        sort(e[i].begin(),e[i].end());
        e[i].erase(unique(e[i].begin(),e[i].end()),e[i].end());
    }
    //for(int i=1;i<=sc;i++) a[i]=sz[i];
    for(int i=1;i<=sc;i++) sz[i]=dfs(i);
    int ans=0;
    for(int i=1;i<=sc;i++) if(sz[i]==n){
        ans+=a[i];
        //cout<<sz[i]<<endl;
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
    
}

signed main(){
    int T=1;
    //cin>>T;
    while(T--){
        sol();
    }
    return 0;
}

易错点

• 多重边必须去重：同一对分量之间可能有多条边，不去重的话 dfs 会把同一个 sz 累加多次 → 用 sort + unique 处理 e[i]。
• sz 的语义在中途变了：Tarjan 结束后它是「分量大小」，dfs 之后它变成「能认可该分量的牛数」。原始分量大小必须先存到 a[i]，否则答案会错。
• 答案可能是 0：没有任何牛被全部认可时输出 0，不要默认至少有一头。
• scc 编号是逆拓扑序：递减方向才是拓扑序方向，别把编号大小当拓扑顺序用。
• 小提示：代码里第一处 for (i = 1; i <= sc; i++) 的排序去重发生在 tarjan 之前（此时 sc == 0），实际不会执行，可以删掉，对答案没有影响。

扩展（可选）

本题还有一种更短的经典做法：缩点后统计每个分量的出度，唯一一个出度为 0 的分量就是答案（若有多个出度为 0 的分量则无解）。 两种做法复杂度都是 O(n + m)，你这份「反图上 DFS 累加」的写法更直观地体现了「被认可」的传递性，也很好。