高速公路

形式化题目

给定一个 $n$ 个点 $m$ 条单向边的有向图。若城市 A 能到达城市 B，且 B 也能到达 A，则 $(A, B)$ 是一个便利城市对（ $(A, B)$ 与 $(B, A)$ 视为同一对）。求便利城市对的数量。

思路

先看一个小数据基准：对每个城市做一次 BFS，直接检查所有城市对是否互相可达。

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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:57
 */
// brute.cpp：对每个城市做 BFS，直接检查互相可达的城市对。
#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    cin >> n >> m;
    vector<vector<int> > graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    // reach[i][j] 表示从城市 i 出发能否到达城市 j。
    vector<vector<int> > reach(n + 1, vector<int>(n + 1));
    for (int start = 1; start <= n; start++) {
        queue<int> q;
        q.push(start);
        reach[start][start] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 0; i < (int)graph[u].size(); i++) {
                int v = graph[u][i];
                if (!reach[start][v]) {
                    reach[start][v] = 1;
                    q.push(v);
                }
            }
        }
    }
    // 统计互相可达的无序城市对。
    long long answer = 0;
    for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) answer += reach[i][j] && reach[j][i];
    cout << answer << '\n';
    return 0;
}

brute.cpp 用一个 reach[i][j] 表格记录可达关系，再两两判断，时间复杂度为 $O(n(n+m))$ ，只适合小数据，但逻辑完全照题意，适合对拍。

关键观察

互相可达的两个城市恰好位于同一个强连通分量：分量内任意两点两两互通，分量之间则单向可达、无法互相到达。

Tarjan 求强连通分量

用 Tarjan 算法找出所有强连通分量。每找到一个大小为 $s$ 的分量，它内部贡献的便利城市对数为：

\binom{s}{2} = \frac{s(s-1)}{2}

累加所有分量的贡献即为答案。注意 $n$ 最大 $10000$ ， $s$ 最大可接近 $n$ ， $s(s-1)/2$ 要用 long long 存储。

代码

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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:57
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
vector<int> graph[MAXN]; // 邻接表存有向图
int dfn[MAXN], low[MAXN]; // 首次访问时间戳与可达的最早时间戳
int in_stack[MAXN];       // 节点是否在 Tarjan 的栈中
int stack_nodes[MAXN];    // Tarjan 栈
int clock_time, stack_size;
long long answer; // 便利城市对总数，用 long long 防溢出

// Tarjan 求强连通分量：栈中同一分量会连续弹出。
void tarjan(int u) {
    dfn[u] = low[u] = ++clock_time;
    stack_nodes[++stack_size] = u;
    in_stack[u] = 1;
    for (int i = 0; i < (int)graph[u].size(); i++) {
        int v = graph[u][i];
        if (dfn[v] == 0) {
            // 树边：递归后尝试用子树的可达时间更新 low[u]。
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            // 回边或横叉边指向栈中节点：说明它们处于同一分量。
            low[u] = min(low[u], dfn[v]);
        }
    }
    // low[u] == dfn[u] 时，u 是所在分量的根，栈顶到 u 之间是完整分量。
    if (low[u] != dfn[u]) return;
    int size = 0;
    while (true) {
        int v = stack_nodes[stack_size--];
        in_stack[v] = 0;
        size++;
        if (v == u) break;
    }
    // 分量内任意两点两两互通，贡献 C(size, 2) 对。
    answer += 1LL * size * (size - 1) / 2;
}

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

    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) if (dfn[i] == 0) tarjan(i);
    cout << answer << '\n';
    return 0;
}

复杂度

时间：Tarjan 每个点和边各访问常数次， $O(n+m)$ 。
空间：邻接表与 Tarjan 栈， $O(n+m)$ 。

总结

“双向可达”直接对应强连通分量，这是有向图问题最常见的转化。求出分量大小后，城市对数量由组合数一次性算出，不需要逐一枚举点对。

目录

形式化题目

思路

关键观察

Tarjan 求强连通分量

代码

复杂度

总结