「一本通 3.5 例 1」受欢迎的牛

形式化题目

给定 $N$ 个点、 $M$ 条有向边的图（ $1 \leqslant N \leqslant 10^4$ ， $1 \leqslant M \leqslant 5 \times 10^4$ ，边可重复），边 $A \to B$ 表示「牛 A 认为牛 B 受欢迎」，可达性按有向路径传递。

求有多少个点 $v$ 满足：其余每个点 $u \neq v$ 都有 $u \to^* v$ 的有向路径（即 $v$ 被除自己外的所有牛认可）。

样例说明

样例输入的边为 $1 \to 2$ 、 $2 \to 1$ 、 $2 \to 3$ 。下图标出分组： $1$ 与 $2$ 互相可达，同属一个强连通分量； $3$ 单独一个分量。

graph LR
    subgraph C1["分量 {1, 2}"]
        n1["1"] --> n2["2"]
        n2 --> n1
    end
    n2 --> n3["分量 {3}"]

$1$ 沿 $1 \to 2 \to 3$ 认为 $3$ 受欢迎， $2$ 沿 $2 \to 3$ 认为 $3$ 受欢迎，所以 $3$ 被 $1$ 、 $2$ 认可；反过来 $3$ 没有出边，不认为 $1$ 、 $2$ 受欢迎，故 $1$ 、 $2$ 都不满足「被除自己外所有牛认可」。答案为 $1$ ，即第 $3$ 头牛。

正解

思路

朴素做法与瓶颈。 对每个点 $v$ 单独判断「所有点是否都能到达 $v$ 」（如从每个点各 BFS 一遍），需要 $O(N(N+M))$ 时间与 $O(N^2)$ 的可达性记录； $N = 10^4$ 时 $N^2 = 10^8$ ，时间和空间都不可接受。瓶颈在于把大量结构相同的点当成独立个体逐个查询。

关键观察：互相可达是等价关系。 若 $u$ 与 $v$ 互相可达，则对任意 $w$ ， $w$ 能到达 $u$ 当且仅当 $w$ 能到达 $v$ （一个方向的路径可以接上环换到另一个点）。因此「被谁可达」的信息在整个强连通分量（SCC）内完全一致，可以把每个 SCC 缩成一个点——缩点后的图一定是 DAG（若缩点后仍有环，环上各点应属同一个 SCC）。

汇点判定。 在缩点 DAG 中，一个分量被全体可达 $\iff$ 它是唯一出度为 $0$ 的汇点：

若汇点唯一：从任意分量沿出边前进，DAG 无环必然终止，只能终止在该汇点，即所有分量都能到达它；
若存在第二个汇点 $C'$ ：两个汇点之间没有路径，原汇点不被 $C'$ 可达，答案为 $0$ 。

缩点后所有点在一个分量内互达，所以答案 = 唯一汇点分量的大小（汇点不唯一则为 $0$ ）。下图是样例缩点后的 DAG，唯一汇点是分量 $\{3\}$ ：

graph LR
    A["{1, 2}"] --> B["{3}"]

求 SCC 用 Kosaraju 两遍 DFS。 第一遍在原图上求后序序列；第二遍按逆后序在反图上 DFS，每次从反图能走到的点集恰为一个 SCC。 $N = 10^4$ 若用递归 DFS 有爆栈风险，因此用显式栈把两遍 DFS 都写成迭代：栈元素为「当前点 + 已走到第几条出边」，走完一个点的全部出边才记入后序。

最后扫一遍边：comp[u] != comp[v] 即缩点图上有边，记下这些分量；全体分量编号减去它们就是汇点集合，大小为 $1$ 时统计该分量的点数。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 15:35
# update_at: 2026-09-30 15:35

import sys


def postorder(n: int, g: list[list[int]]) -> list[int]:
    """原图上迭代 DFS 的后序序列：Kosaraju 第一遍，后走完的点先被第二遍处理。"""
    seen = [False] * n
    order: list[int] = []
    for start in range(n):
        if seen[start]:
            continue
        seen[start] = True
        stack = [(start, 0)]  # (点, 已走到第几条出边)
        while stack:
            v, i = stack.pop()
            if i < len(g[v]):
                stack.append((v, i + 1))   # 回溯后从下一条出边继续
                w = g[v][i]
                if not seen[w]:
                    seen[w] = True
                    stack.append((w, 0))
            else:
                order.append(v)            # 所有出边走完才入序，即后序
    return order


def assign_components(n: int, rg: list[list[int]], order: list[int]) -> list[int]:
    """反图上按逆后序 DFS 染色，返回每个点所属强连通分量编号（从 0 连续）。"""
    comp = [-1] * n
    cid = 0
    for start in reversed(order):
        if comp[start] != -1:
            continue
        comp[start] = cid
        stack = [start]
        while stack:
            v = stack.pop()
            for w in rg[v]:
                if comp[w] == -1:          # 同一次反图 DFS 能到的点都属本分量
                    comp[w] = cid
                    stack.append(w)
        cid += 1
    return comp


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    g: list[list[int]] = [[] for _ in range(n)]
    rg: list[list[int]] = [[] for _ in range(n)]
    for _ in range(m):
        a, b = next(data) - 1, next(data) - 1  # 转 0 起下标
        g[a].append(b)
        rg[b].append(a)

    comp = assign_components(n, rg, postorder(n, g))

    # 缩点 DAG 中出度为 0 的分量才能被全员认可；答案 = 唯一汇点分量的大小
    has_out = {comp[u] for u, vs in enumerate(g) for v in vs if comp[v] != comp[u]}
    sinks = {cid for cid in range(max(comp) + 1)} - has_out
    popular = next(iter(sinks)) if len(sinks) == 1 else -1
    print(sum(1 for c in comp if c == popular) if popular != -1 else 0)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:37
 * update_at: 2026-10-05 05:37
 */

// 受欢迎的牛：Kosaraju 两遍 DFS 求 SCC 缩点，
// 被除自己外所有牛认可 <=> 缩点 DAG 中唯一出度为 0 的汇点，答案为该分量大小。

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

const int MAXN = 10005;
const int MAXM = 50005;

typedef long long ll;

// 链式前向星：正图 g，反图 rg
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;
int rhead[MAXN], rto[MAXM], rnxt[MAXM], redge_cnt;

int n, m;
int comp[MAXN];     // comp[v] = 点 v 所属强连通分量编号
int out_comp[MAXN]; // out_comp[c] = 分量 c 在缩点图上是否有指向别的分量的出边
bool vis[MAXN];
int order_[MAXN];   // 第一遍 DFS 的后序序列
int order_cnt;
int stk[MAXN];      // 迭代 DFS 的显式栈：stk 存点，edge_ptr 存已走到第几条边
int edge_ptr[MAXN];
ll ans;

// 正图加边 u -> v。
void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 反图加边（方向取反）。
void add_redge(int u, int v) {
    redge_cnt++;
    rto[redge_cnt] = v;
    rnxt[redge_cnt] = rhead[u];
    rhead[u] = redge_cnt;
}

// 第一遍 DFS：原图上求后序序列，走完一个点的全部出边才入序。
// N 达 1e4，递归可能爆栈，用显式栈迭代实现。
void dfs_order(int s) {
    int top = 0;
    stk[top++] = s;
    edge_ptr[s] = head[s];
    vis[s] = true;
    while (top > 0) {
        int u = stk[top - 1];
        int e = edge_ptr[u];
        if (e != 0) {
            edge_ptr[u] = nxt[e]; // 记录回溯后从下一条出边继续
            int v = to[e];
            if (!vis[v]) {
                vis[v] = true;
                stk[top++] = v;
                edge_ptr[v] = head[v];
            }
        } else {
            // 出边全部走完，记入后序
            top--;
            order_cnt++;
            order_[order_cnt] = u;
        }
    }
}

// 第二遍 DFS：反图上从 s 能走到的点都属于同一个 SCC。
void dfs_assign(int s, int cid) {
    int top = 0;
    stk[top++] = s;
    comp[s] = cid;
    while (top > 0) {
        int u = stk[--top];
        for (int e = rhead[u]; e != 0; e = rnxt[e]) {
            int v = rto[e];
            if (comp[v] == 0) {
                comp[v] = cid;
                stk[top++] = v;
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add_edge(a, b);
        add_redge(b, a);
    }

    // Kosaraju 第一遍：对每个未访问点求后序
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs_order(i);
        }
    }

    // 第二遍：按逆后序在反图上染色
    int cid = 0; // 分量编号从 1 开始，comp[v] == 0 表示未染色
    for (int i = n; i >= 1; i--) {
        int u = order_[i];
        if (comp[u] == 0) {
            cid++;
            dfs_assign(u, cid);
        }
    }

    // 扫一遍边：comp[u] != comp[v] 即缩点图上有出边，标记该分量不是汇点
    for (int u = 1; u <= n; u++) {
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            if (comp[u] != comp[v]) {
                out_comp[comp[u]] = 1;
            }
        }
    }

    // 汇点唯一时答案为该分量大小；有多个汇点则答案为 0
    int sink = 0;
    bool unique_sink = true;
    for (int c = 1; c <= cid; c++) {
        if (out_comp[c] == 0) {
            if (sink != 0) {
                unique_sink = false; // 出现第二个汇点
            }
            sink = c;
        }
    }

    if (!unique_sink) {
        ans = 0;
    } else {
        for (int v = 1; v <= n; v++) {
            if (comp[v] == sink) ans++;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度

时间 $O(N + M)$ ：两遍 DFS 各访问每点每边常数次，出度统计再扫 $M$ 条边。与 C++ 正解（Kosaraju / Tarjan）同阶。
空间 $O(N + M)$ ：正图、反图邻接表与若干 $O(N)$ 数组。

总结

「被全员认可的点」是传递闭包查询，逐点求可达性是 $O(N^2)$ 瓶颈；利用互相可达的等价性把图缩成 DAG 后，问题坍缩成一个常数级判定——唯一出度为 $0$ 的汇点是否存在，存在则答案为其分量大小。整题即「Kosaraju 缩点 + 汇点计数」， $O(N + M)$ 一步到位。

验证：仓库真实数据 data/popular1..13 全部 PASS（verify.sh，13/13，最长 0.034s / 峰值 25.1MB）。