受欢迎的牛

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1890 字
Tarjan缩点统计出度为零的分量
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1513
// 题意：N 头牛 M 条「A 认为 B 受欢迎」的有向边且关系可传递，求被除自己外所有牛认为受欢迎的牛的数量。
// 思路：Tarjan 缩点后，若缩点 DAG 中出度为 0 的点恰好只有一个，该强连通分量的大小即为答案，否则答案为 0。
// 1. 出度为 0 的分量能被所有其它分量到达，是唯一可能的「明星」候选。
// 2. 重复的 (A, B) 边不影响连通性，也不影响出度统计，不必去重。
// 复杂度：O(n + m) 时间 / O(n + m) 空间
// 易错点：必须统计缩点后分量的出度，直接用原图点的出度会把分量内部的边算进去。
// 易错点：出度为 0 的分量多于一个时它们互不可达，答案是 0 而不是各分量大小之和。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
const int MAXM = 50005;
int head[MAXN], to[MAXM], nxt[MAXM], ecnt;
int dfn[MAXN], low[MAXN], stk[MAXN], top, idx;
int scc[MAXN], sz[MAXN], scnt;
bool instk[MAXN];
int out[MAXN];
void add(int u, int v){
    to[++ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
}
void tarjan(int u){
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    instk[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(instk[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]){
        scnt++;
        while(true){
            int x = stk[top--];
            instk[x] = false;
            scc[x] = scnt;
            sz[scnt]++;
            if(x == u) break;
        }
    }
}
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++){
        for(int i = head[u]; i; i = nxt[i]){
            int v = to[i];
            if(scc[u] != scc[v]) out[scc[u]] = 1;
        }
    }
    int cnt = 0;
    int ans = 0;
    for(int i = 1; i <= scnt; i++){
        if(!out[i]){
            cnt++;
            ans = sz[i];
        }
    }
    if(cnt == 1) cout << ans << "\n";
    else cout << 0 << "\n";
    return 0;
}
受欢迎的牛

正文

一本通·提高篇的其它内容
