「一本通 3.5 例 2」最大半连通子图

形式化题目

给定一个包含 $N$ 个节点、 $M$ 条有向边的有向图 $G = (V, E)$ ，以及模数 $X$ 。

定义：

半连通图：若有向图满足对任意节点对 $u, v \in V$ ，至少存在一条 $u \to v$ 或 $v \to u$ 的有向路径，则称该图是半连通的。
半连通导出子图：选出点集 $V' \subseteq V$ 构成的导出子图 $G[V']$ ，若 $G[V']$ 是半连通的，则称其为半连通子图。

计算任务：

求最大半连通导出子图包含的最大节点数 $K$ ；
求节点数等于 $K$ 的不同最大半连通导出子图的数量 $C \pmod X$ 。

样例说明与图示

以样例为例：

text

1
2
3
4
5
6
76 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

原图的结构如下：

graph TD
    1((1)) <--> 2((2))
    1 --> 3((3))
    2 --> 4((4))
    5((5)) --> 6((6))
    6 --> 4

分析原图中的连通性：

节点 $1$ 与节点 $2$ 互相可达，构成一个大小为 $2$ 的强连通分量 (SCC)。
其余节点 $\{3\}, \{4\}, \{5\}, \{6\}$ 各自构成大小为 $1$ 的强连通分量。

将各强连通分量缩点后的 DAG 结构如下（括号内为分量包含的原图节点数）：

graph TD
    SCC1["SCC 1: {1, 2} (大小: 2)"] --> SCC3["SCC 3: {3} (大小: 1)"]
    SCC1 --> SCC4["SCC 4: {4} (大小: 1)"]
    SCC5["SCC 5: {5} (大小: 1)"] --> SCC6["SCC 6: {6} (大小: 1)"]
    SCC6 --> SCC4

寻找包含最多原图节点数的半连通子图，即寻找 DAG 上点权和最大的路径：

路径 SCC 1 -> SCC 3：包含原图点 $\{1, 2, 3\}$ ，点数为 $2 + 1 = 3$ 。
路径 SCC 1 -> SCC 4：包含原图点 $\{1, 2, 4\}$ ，点数为 $2 + 1 = 3$ 。
路径 SCC 5 -> SCC 6 -> SCC 4：包含原图点 $\{5, 6, 4\}$ ，点数为 $1 + 1 + 1 = 3$ 。

因此，最大半连通子图的点数为 $3$ ，方案共有 $3$ 种，输出 3 和 3。

解法：Tarjan 缩点 + DAG 拓扑排序 DP

思路

1. 强连通分量 (SCC) 的性质

在同一个强连通分量中，任意两个节点之间都双向可达。因此，同一个强连通分量内部天然满足半连通性质。若某个半连通导出子图包含了某个强连通分量内的某一个点，那么将该分量内的所有其余点也加入该子图，子图仍然保持半连通：

对于该分量内部的点，互相有路径。
对于外部点，若已有路径连接该分量的某个点，则通过分量内部的双向连通性，也可通达该分量内的所有点。

为了让子图包含的节点数最大，同一个强连通分量中的节点在最大半连通子图中必然“要么全选，要么全不选”。

2. DAG 上的半连通性等价于“链”

利用 Tarjan 算法将原图中的强连通分量缩点，得到一个有向无环图 (DAG)，每个新节点的权值为对应强连通分量的节点数。

在 DAG 中，若选出一组节点 $V'_{scc}$ 构成半连通导出子图：

任意两点 $u, v \in V'_{scc}$ 必须有一方能够到达另一方；
在无环的有向图中，这意味着选出的所有点在拓扑序上必须构成一条严格前趋后继的单向路径（即简单链 $u_1 \to u_2 \to \dots \to u_k$ ）。
若存在两个选出的节点没有路径可达，则不符合半连通要求。

因此，原图的最大半连通子图与缩点后 DAG 上的“最大点权路径（最长链）”一一对应！

3. 边的去重与拓扑 DP

在原图中，可能有多个跨分量的边连接相同的两个 SCC，缩点后会产生重边与自环。

自环无需保留；
重边如果保留，在拓扑 DP 累加路径方案数时会导致同一条转移路径被重复计数，因此必须对缩点后的边去重。

去重后，在 DAG 上通过拓扑排序进行动态规划：

设 $dp\_len[u]$ 表示以 DAG 节点 $u$ 结尾的最长链点权和；
设 $dp\_cnt[u]$ 表示以 $u$ 结尾、且点权和达到 $dp\_len[u]$ 的链方案数。

状态初始化：

对于所有入度为 $0$ 的节点 $u$ ：
$dp\_len[u] = scc\_size[u],\quad dp\_cnt[u] = 1$

状态转移：对于每条 DAG 有向边 $u \to v$ ：

若 $dp\_len[u] + scc\_size[v] > dp\_len[v]$ ：
$dp\_len[v] = dp\_len[u] + scc\_size[v],\quad dp\_cnt[v] = dp\_cnt[u]$
若 $dp\_len[u] + scc\_size[v] == dp\_len[v]$ ：
$dp\_cnt[v] = (dp\_cnt[v] + dp\_cnt[u]) \pmod X$

遍历完成后，全图最大点数 $K = \max_{u} dp\_len[u]$ ；最大点数的方案总数 $C = \sum_{dp\_len[u] = K} dp\_cnt[u] \pmod X$ 。

代码

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
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#!/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-05-22 19:17
# update_at: 2026-05-22 19:17

import sys


def tarjan_scc(n: int, adj: list[list[int]]) -> tuple[int, list[int], list[int]]:
    """用 Tarjan 算法缩点，返回 (scc 数量, 每个原点的 scc 编号, 每个 scc 的点权/大小)。

    由于递归在 N=10^5 时深度极大，使用非递归显式栈模拟 DFS。
    """
    dfn = [0] * (n + 1)
    low = [0] * (n + 1)
    scc = [0] * (n + 1)
    in_stk = [False] * (n + 1)
    stk: list[int] = []
    timer = 0
    scc_cnt = 0
    scc_size = [0]  # 下标 1-based

    # 显式栈模拟 Tarjan DFS: (u, edge_index)
    for root in range(1, n + 1):
        if dfn[root]:
            continue
        call_stk = [(root, 0)]
        timer += 1
        dfn[root] = low[root] = timer
        stk.append(root)
        in_stk[root] = True

        while call_stk:
            u, i = call_stk[-1]
            if i < len(adj[u]):
                call_stk[-1] = (u, i + 1)
                v = adj[u][i]
                if not dfn[v]:
                    timer += 1
                    dfn[v] = low[v] = timer
                    stk.append(v)
                    in_stk[v] = True
                    call_stk.append((v, 0))
                elif in_stk[v] and dfn[v] < low[u]:
                    low[u] = dfn[v]
            else:
                call_stk.pop()
                if call_stk:
                    p = call_stk[-1][0]
                    if low[u] < low[p]:
                        low[p] = low[u]
                if dfn[u] == low[u]:
                    scc_cnt += 1
                    sz = 0
                    while True:
                        node = stk.pop()
                        in_stk[node] = False
                        scc[node] = scc_cnt
                        sz += 1
                        if node == u:
                            break
                    scc_size.append(sz)

    return scc_cnt, scc, scc_size


def build_dag(
    n: int, scc_cnt: int, scc: list[int], edges: list[tuple[int, int]]
) -> tuple[list[list[int]], list[int]]:
    """在强连通分量间建立无重边 DAG，并统计每个新点的入度。"""
    # 边去重：先映射为 (scc[u], scc[v])，去除自环和重边
    scc_edges = sorted(
        (scc[u], scc[v]) for u, v in edges if scc[u] != scc[v]
    )
    dag: list[list[int]] = [[] for _ in range(scc_cnt + 1)]
    in_deg = [0] * (scc_cnt + 1)

    prev_edge = (0, 0)
    for edge in scc_edges:
        if edge != prev_edge:
            u, v = edge
            dag[u].append(v)
            in_deg[v] += 1
            prev_edge = edge

    return dag, in_deg


def find_longest_chain(
    scc_cnt: int, dag: list[list[int]], in_deg: list[int], scc_size: list[int], mod: int
) -> tuple[int, int]:
    """在 DAG 上拓扑排序求最长链的点权和以及方案数。"""
    # 拓扑排序队列：初始入度为 0 的节点
    queue = [u for u in range(1, scc_cnt + 1) if in_deg[u] == 0]
    dp_len = [0] * (scc_cnt + 1)
    dp_cnt = [0] * (scc_cnt + 1)

    for u in queue:
        dp_len[u] = scc_size[u]
        dp_cnt[u] = 1

    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        for v in dag[u]:
            cand_len = dp_len[u] + scc_size[v]
            if cand_len > dp_len[v]:
                dp_len[v] = cand_len
                dp_cnt[v] = dp_cnt[u]
            elif cand_len == dp_len[v]:
                dp_cnt[v] = (dp_cnt[v] + dp_cnt[u]) % mod

            in_deg[v] -= 1
            if in_deg[v] == 0:
                queue.append(v)

    max_len = max(dp_len)
    total_cnt = sum(
        dp_cnt[u] for u in range(1, scc_cnt + 1) if dp_len[u] == max_len
    ) % mod
    return max_len, total_cnt


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    mod = int(next(it))

    edges: list[tuple[int, int]] = []
    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(next(it))
        v = int(next(it))
        edges.append((u, v))
        adj[u].append(v)

    scc_cnt, scc, scc_size = tarjan_scc(n, adj)
    dag, in_deg = build_dag(n, scc_cnt, scc, edges)
    max_len, total_cnt = find_longest_chain(scc_cnt, dag, in_deg, scc_size, mod)

    print(max_len)
    print(total_cnt)


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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212/**
 * 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:42
 * update_at: 2026-10-05 05:42
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 100005;   // 点数上限
const int MAXM = 1000005;  // 边数上限

// 原图，链式前向星存边
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;

// Tarjan 缩点所需数组
int dfn[MAXN], low[MAXN], scc_id[MAXN], scc_size[MAXN];
int scc_cnt, timer;
int stk[MAXN], stk_top;   // Tarjan 的已访问栈
bool in_stk[MAXN];
int dfs_node[MAXN], dfs_edge[MAXN], dfs_top; // 非递归 DFS 的调用栈：当前点、下一条待走的边

// 缩点后的 DAG：先用 ll 编码所有跨分量边，排序去重后再建邻接表
ll dag_key[MAXM];         // dag_key[j] = a * (scc_cnt + 1) + b，表示分量 a -> 分量 b
int dag_head[MAXN], dag_nxt[MAXM];
int dag_indeg[MAXN];

// DAG 上拓扑 DP：dp_len 为以该分量结尾的最长链点权和，dp_cnt 为该长度的链方案数
ll dp_len[MAXN], dp_cnt[MAXN];
int que[MAXN];

ll n, m, mod_value;

// 加一条原图边 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 read_input() {
    scanf("%lld %lld %lld", &n, &m, &mod_value);
    for (ll i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(u, v);
    }
}

// 非递归 Tarjan 求强连通分量：把点的 DFS 调用栈显式写成数组，避免 N=10^5 时递归爆栈。
void tarjan() {
    for (int root = 1; root <= n; root++) {
        if (dfn[root] != 0) {
            continue;
        }

        timer++;
        dfn[root] = low[root] = timer;
        stk_top++;
        stk[stk_top] = root;
        in_stk[root] = true;

        dfs_top = 0;
        dfs_top++;
        dfs_node[dfs_top] = root;
        dfs_edge[dfs_top] = head[root];

        while (dfs_top > 0) {
            int u = dfs_node[dfs_top];
            int e = dfs_edge[dfs_top];

            if (e != 0) {
                // 先把当前点的边指针后移，再处理这条边
                dfs_edge[dfs_top] = nxt[e];
                int v = to[e];
                if (dfn[v] == 0) {
                    timer++;
                    dfn[v] = low[v] = timer;
                    stk_top++;
                    stk[stk_top] = v;
                    in_stk[v] = true;
                    dfs_top++;
                    dfs_node[dfs_top] = v;
                    dfs_edge[dfs_top] = head[v];
                } else if (in_stk[v] && dfn[v] < low[u]) {
                    low[u] = dfn[v];
                }
            } else {
                // u 的所有出边走完，回溯时用儿子的 low 更新父亲
                dfs_top--;
                if (dfs_top > 0) {
                    int p = dfs_node[dfs_top];
                    if (low[u] < low[p]) {
                        low[p] = low[u];
                    }
                }
                if (dfn[u] == low[u]) {
                    scc_cnt++;
                    int sz = 0;
                    while (true) {
                        int x = stk[stk_top];
                        stk_top--;
                        in_stk[x] = false;
                        scc_id[x] = scc_cnt;
                        sz++;
                        if (x == u) {
                            break;
                        }
                    }
                    scc_size[scc_cnt] = sz;
                }
            }
        }
    }
}

// 建缩点后的无重边无自环 DAG，并统计入度。重边会让方案数被重复累加，必须去重。
void build_dag() {
    ll base = scc_cnt + 1;
    int key_cnt = 0;
    for (int u = 1; u <= n; u++) {
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            int a = scc_id[u];
            int b = scc_id[v];
            if (a != b) {
                key_cnt++;
                dag_key[key_cnt] = (ll)a * base + b;
            }
        }
    }

    sort(dag_key + 1, dag_key + key_cnt + 1);

    int unique_cnt = 0;
    for (int i = 1; i <= key_cnt; i++) {
        if (i == 1 || dag_key[i] != dag_key[i - 1]) {
            unique_cnt++;
            dag_key[unique_cnt] = dag_key[i];
        }
    }

    for (int j = 1; j <= unique_cnt; j++) {
        int a = dag_key[j] / base;
        int b = dag_key[j] % base;
        dag_nxt[j] = dag_head[a];
        dag_head[a] = j;
        dag_indeg[b]++;
    }
}

// 在 DAG 上拓扑排序，求最大点权链 K 与方案数 C mod X。
void solve_dag() {
    int qhead = 0, qtail = 0;
    for (int u = 1; u <= scc_cnt; u++) {
        if (dag_indeg[u] == 0) {
            dp_len[u] = scc_size[u];
            dp_cnt[u] = 1;
            qtail++;
            que[qtail] = u;
        }
    }

    ll base = scc_cnt + 1;
    while (qhead < qtail) {
        qhead++;
        int u = que[qhead];
        for (int j = dag_head[u]; j != 0; j = dag_nxt[j]) {
            int v = dag_key[j] % base;
            ll cand = dp_len[u] + scc_size[v];
            if (cand > dp_len[v]) {
                dp_len[v] = cand;
                dp_cnt[v] = dp_cnt[u];
            } else if (cand == dp_len[v]) {
                dp_cnt[v] = (dp_cnt[v] + dp_cnt[u]) % mod_value;
            }
            dag_indeg[v]--;
            if (dag_indeg[v] == 0) {
                qtail++;
                que[qtail] = v;
            }
        }
    }

    ll best_len = 0;
    ll best_cnt = 0;
    for (int u = 1; u <= scc_cnt; u++) {
        if (dp_len[u] > best_len) {
            best_len = dp_len[u];
        }
    }
    for (int u = 1; u <= scc_cnt; u++) {
        if (dp_len[u] == best_len) {
            best_cnt = (best_cnt + dp_cnt[u]) % mod_value;
        }
    }

    printf("%lld\n%lld\n", best_len, best_cnt);
}

int main() {
    read_input();
    tarjan();
    build_dag();
    solve_dag();
    return 0;
}

复杂度

时间复杂度： $O(N + M \log M)$ 。Tarjan 缩点遍历全图所有点和边需 $O(N + M)$ 时间；对缩点后的边进行排序去重需 $O(M \log M)$ ；DAG 拓扑排序及 DP 遍历每个点与去重后的边需 $O(N + M)$ 。总时间可在 1 秒内高效完成。
空间复杂度： $O(N + M)$ 。需要存储原图和 DAG 的邻接表、Tarjan 显式栈、时间戳数组以及 DP 状态数组。

总结

模型转化：通过对图的连通性分析，发现强连通分量内的节点具有“全选或全不选”的属性，从而将有向图问题通过 Tarjan 缩点转化为 DAG 问题。
结构等价：利用有向无环图的拓扑偏序特性，将半连通性约束自然规约为 DAG 上的“一条简单路径”，将复杂子图选择问题转化为经典的最长路问题。
细节严谨：统计路径方案数时，缩点后产生的重边会干扰计数，必须预先进行边去重以避免重复累计方案。