答案拆成与删边无关的基线 T0 加上桥的贡献 s*(C-s):并查集算 T0,迭代式 Tarjan 求桥与 DFS 子树大小,回答每次询问 O(1)。
OJ: roj
题目 ID: 1734
难度:提高+/省选-
标签:图论Tarjan割边并查集cpppython
创建: 2026-10-07 20:30
更新: 2026-10-07 20:30
形式化题目
给一个
形式化地,设
注意统计的是全图的不可达点对,删边前就已经不连通的点对也算在内——这一点由样例唯一确定:
样例里点
正解
思路
先处理"删边前"。 不管删哪条边,删之前全图就已经互不可达的点对始终是同一批,
它们的贡献与
求每个块的大小用并查集(带大小合并)即可,int,必须用 64 位整数(long long / Python 任意精度)。
样例里
再看删边带来的变化。 删一条边
- 若
不是桥, 仍然连通,块结构一点没变,故 ; - 若
是桥, 被切成两块 、 ,大小分别记 与 。 原本 内部两两可达(贡献 ),现在 与 之间的点对全部变成不可达, 而这些点对的数量正是 。故 。
于是问题变成:对每条边,
判定桥 + 取子树大小。 这是 Tarjan 求桥的标准做法。对图做 DFS,记 dfn[u] 为时间戳、
low[u] 为 dfn,则对 DFS 树上的父边
为什么这个判据和"切下来的大小"是同一件事:DFS 树中 low[u] > dfn[p] 说明这棵子树没有任何一条边能通到 sub[u]。所以一次 DFS 同时得到桥的集合与每条桥的
重边与自环。 这两个是本题最容易写错的地方。
- 自环永远不是桥(删掉它两个端点仍是同一个点,连通性不变)。Tarjan 里自环表现为
一条
v == u的边,它的dfn[v]已经赋过值,只会用来更新low[u],不会影响判定。 - 两条平行边都不是桥:删掉一条后两个端点还能靠另一条连通。判桥时要跳过父边以避免
“儿子顺着树边爬回父亲”;如果按父顶点跳(
v == parent[u]就不看),那么第二条平行边 也会被当成父边忽略掉,于是low[u]停留在dfn[u],low[u] > dfn[p]成立 → 误判成桥。 正确做法是只跳过父边的编号pe[u](一条无向边存两条弧, 用 e >> 1还原边号):这样另一条平行边会被当作返祖边,把low[u]拉到dfn[p],判据不成立。 样例第两条边就是一对平行边 、 ,它们的答案 正好检验这一点。
实现细节:为什么用迭代 DFS。 it[u],
it[u] 走完时弹出并回溯——回溯那一瞬间才能拿到子树已经算好的 sub[u] 与 low[u],
正是这一瞬间做"累加子树大小 + 判桥"两件事。所以不能用 BFS 顺序代替,必须保序地模拟 DFS。
顺带一提,删边后"互不可达点对"也可以直接从块的分布算:
代码
Python 版:
#!/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-10-07 20:30
# update_at: 2026-10-07 20:30
import sys
# 类型别名:链式前向星三元组 (head, to, nxt);第 i 条输入边占弧 2i 与 2i+1
# head/nxt 里的 -1 是哨兵,表示"后面没有弧了"
type Star = tuple[list[int], list[int], list[int]]
# 两个等长的 int 列表:(并查集父亲, 每块大小) 或 (桥对应子树根, DFS 子树大小)
type ListPair = tuple[list[int], list[int]]
def build_star(n: int, m: int, ends: list[int]) -> Star:
"""建无向图的链式前向星;第 i 条输入边的两端是 ends[2i]、ends[2i+1]。"""
head = [-1] * n
to = [0] * (2 * m)
nxt = [-1] * (2 * m)
for i in range(m):
u, v = ends[2 * i], ends[2 * i + 1]
e = i << 1
to[e], nxt[e], head[u] = v, head[u], e
to[e + 1], nxt[e + 1], head[v] = u, head[v], e + 1
return head, to, nxt
def find_root(fa: list[int], x: int) -> int:
"""并查集找根(带路径折半);fa 上是父亲,根的父亲是自己。"""
while fa[x] != x:
fa[x] = fa[fa[x]]
x = fa[x]
return x
def build_dsu(n: int, m: int, ends: list[int]) -> ListPair:
"""并查集 + 每块大小:只有根的 sz 有效,用来 O(1) 取任意点所在连通块大小。"""
fa = list(range(n))
sz = [1] * n
for i in range(m):
a, b = find_root(fa, ends[2 * i]), find_root(fa, ends[2 * i + 1])
if a == b:
continue
if sz[a] < sz[b]:
a, b = b, a
fa[b] = a
sz[a] += sz[b]
return fa, sz
def count_unreachable0(n: int, fa: list[int], sz: list[int]) -> int:
"""T0 = C(n,2) - Σ 每块 C(块大小,2):删边前就已经互不可达的无序点对数。"""
total = n * (n - 1) // 2
for r in range(n):
if fa[r] == r: # 只在根上统计一次
total -= sz[r] * (sz[r] - 1) // 2
return total
def find_bridges(n: int, m: int, star: Star) -> ListPair:
"""迭代式 Tarjan:返回 (bridge_child, sub),对应 C++ 版的同名数组。
bridge_child[x] = 边 x 是桥时被切下的那侧子树根(否则 -1);sub[v] = DFS 子树点数。
必须按「父边编号」跳过父边(e >> 1),否则平行重边会被误判成桥;自环不影响连通性。
"""
head, to, nxt = star
dfn = [0] * n # DFS 序,0 表示未访问
low = [0] * n # 能回溯到的最小 dfn
pe = [-1] * n # DFS 树中的父边编号
sub = [0] * n # DFS 树子树点数
it = head[:] # 当前出弧指针
bridge_child = [-1] * m
timer = 0
for s in range(n):
if dfn[s]:
continue
timer += 1
dfn[s] = low[s] = timer
sub[s] = 1
stack = [s]
while stack:
u = stack[-1]
e = it[u]
if e != -1:
it[u] = nxt[e]
if (e >> 1) == pe[u]:
continue # 父边的两个方向都不走
v = to[e]
if dfn[v] == 0:
timer += 1
dfn[v] = low[v] = timer
sub[v] = 1
pe[v] = e >> 1
it[v] = head[v]
stack.append(v)
elif dfn[v] < low[u]:
low[u] = dfn[v] # 返祖边(含重边里指向祖先的那一条)
else:
stack.pop() # u 的出弧走完,回溯到父亲 p
if stack:
p = stack[-1]
sub[p] += sub[u]
if low[u] < low[p]:
low[p] = low[u]
if low[u] > dfn[p]: # 子树回不到 p → 父边是桥
bridge_child[pe[u]] = u # 记下切走的那侧子树根
return bridge_child, sub
def answer_queries(fa: list[int], sz: list[int], sub: list[int], bridge_child: list[int],
unreachable0: int, queries: list[int]) -> list[str]:
"""逐条回答询问:桥的答案 = T0 + s*(C-s),其余边就是 T0;输出只保留后三位。"""
out: list[str] = []
for x in queries:
ans = unreachable0
cuts = bridge_child[x]
if cuts >= 0: # 是桥:连通块被切成 s 与 C-s 两块
block = sz[find_root(fa, cuts)] # 该边所在连通块大小 C
ans += sub[cuts] * (block - sub[cuts]) # 新增互不可达点对 s*(C-s)
out.append(str(ans % 1000)) # 题面要求只保留后三位
return out
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m, Q = next(data), next(data), next(data)
ends = [next(data) for _ in range(2 * m)] # 第 i 条边的两端紧挨着
queries = [next(data) for _ in range(Q)]
star = build_star(n, m, ends)
fa, sz = build_dsu(n, m, ends)
unreachable0 = count_unreachable0(n, fa, sz)
bridge_child, sub = find_bridges(n, m, star)
answers = answer_queries(fa, sz, sub, bridge_child, unreachable0, queries)
sys.stdout.write('\n'.join(answers) + '\n')
if __name__ == "__main__":
solve()C++ 版(同一算法,加了自己写的读写缓冲以应对
/**
* 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-07 20:30
* update_at: 2026-10-07 20:30
*/
// 一本通 1734《删边问题》(对应 roj 1734)
//
// 题意:无向图 n 个点 m 条边(点、边从 0 编号,允许重边与自环),Q 次询问,
// 每次给出边编号 x,问删掉这条边之后全图有多少个无序点对 (u, v) 互不可达,
// 答案模 1000 输出。
//
// 关键观察:删一条边只可能把「原本连通的那块」拆开,且只有该边是桥时连通性才变。
// 设该边所在连通块大小为 C,桥把 DFS 树子树部分(大小 s)与其余部分切开,
// 则新增互不可达点对 s * (C - s);删非桥边(重边之一、自环、环上的边)答案不变。
// 于是 ans(x) = T0 + [x 是桥] * s * (C - s),T0 = C(n,2) - Σ C(块大小,2)。
//
// 判定桥用 Tarjan:low[v] > dfn[u] 时树边 (u,v) 是桥。重边必须按「父边编号」跳过,
// 不能按「父顶点」跳过,否则两条平行边会互相看不到、被误判成桥。
//
// 复杂度 O(n + m + Q);n,m,Q 最大 1e5/1e6/8e5,故 DFS 用显式栈迭代实现,防链状图爆栈。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100000 + 10; // 点编号上界(题面 n <= 1e5)
const int MAXM = 1000000 + 10; // 边编号上界(题面 m <= 1e6)
const int MAXARC = MAXM * 2 + 10; // 每条无向边存两条弧
int n, m, Q;
// ---------------- 快速读入 / 输出(1e6 条边 + 8e5 次询问,cin 有超时风险)----------------
namespace FastIO {
const int BUFSIZE = 1 << 16;
char in_buf[BUFSIZE];
ll in_pos = 0, in_len = 0;
// 取一个字符;缓冲区空了就补一次读,文件结束返回 -1
int read_char() {
if (in_pos == in_len) {
in_len = fread(in_buf, 1, BUFSIZE, stdin);
in_pos = 0;
if (in_len <= 0) return -1;
}
return in_buf[in_pos++];
}
// 跳过空白后读一个非负整数
int read_int() {
int c = read_char();
while (c != -1 && (c < '0' || c > '9')) c = read_char();
if (c == -1) return -1;
int x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = read_char();
}
return x;
}
char out_buf[BUFSIZE];
int out_pos = 0;
void flush_out() {
if (out_pos > 0) {
fwrite(out_buf, 1, out_pos, stdout);
out_pos = 0;
}
}
void write_char(char c) {
if (out_pos == BUFSIZE) flush_out();
out_buf[out_pos++] = c;
}
// 答案一定非负且已经模过 1000,逆序放数字再正序输出,末尾补换行
void write_int(ll x) {
char tmp[8];
int len = 0;
if (x == 0) tmp[len++] = '0';
while (x > 0) {
tmp[len++] = '0' + x % 10;
x /= 10;
}
while (len > 0) write_char(tmp[--len]);
write_char('\n');
}
} // namespace FastIO
// ---------------- 链式前向星:第 i 条输入边对应弧 2i 与 2i+1 ----------------
int head[MAXN]; // head[u] 是 u 的第一条出弧编号,-1 表示无边
int arc_to[MAXARC]; // 弧的终点
int arc_nxt[MAXARC]; // 同一起点的下一条弧
int arc_cnt = 0;
// 加一条无向边 u-v;第 i 条输入边的两条弧编号恰为 2i 与 2i+1
void add_edge(int u, int v) {
arc_to[arc_cnt] = v;
arc_nxt[arc_cnt] = head[u];
head[u] = arc_cnt++;
arc_to[arc_cnt] = u;
arc_nxt[arc_cnt] = head[v];
head[v] = arc_cnt++;
}
// ---------------- 并查集:求连通块大小,算 T0 ----------------
struct DsuNode {
int fa; // 父亲,根的父亲是自己
int sz; // 只在根上有效:连通块点数
};
DsuNode dsu[MAXN];
int find_root(int x) {
while (dsu[x].fa != x) {
dsu[x].fa = dsu[dsu[x].fa].fa; // 路径折半
x = dsu[x].fa;
}
return x;
}
void merge_node(int a, int b) {
a = find_root(a);
b = find_root(b);
if (a == b) return;
if (dsu[a].sz < dsu[b].sz) swap(a, b);
dsu[b].fa = a;
dsu[a].sz += dsu[b].sz;
}
// ---------------- 每个点在 DFS 树里的信息聚合在一起 ----------------
struct Vertex {
int dfn; // DFS 序,0 表示还没访问
int low; // 能回溯到的最小 dfn
int pe; // DFS 树中的父边编号,-1 表示是根
int sub; // DFS 树子树点数
int it; // 显式栈 DFS 的当前出弧指针
};
Vertex ver[MAXN];
int bridge_child[MAXM]; // 边编号 -> 它是桥时对应子树根;非桥保持 -1
int dfs_stack[MAXN]; // 显式栈(顶点编号),替代递归
ll unreachable0; // T0:删边前全图互不可达的无序点对数
void read_input() {
n = FastIO::read_int();
m = FastIO::read_int();
Q = FastIO::read_int();
for (int i = 0; i < n; i++) {
head[i] = -1;
dsu[i].fa = i;
dsu[i].sz = 1;
ver[i].dfn = 0;
ver[i].pe = -1;
}
for (int i = 0; i < m; i++) bridge_child[i] = -1;
for (int i = 0; i < m; i++) {
int u = FastIO::read_int();
int v = FastIO::read_int();
add_edge(u, v); // 自环/重边原样保留,Tarjan 会正确处理
merge_node(u, v);
}
}
// T0 = C(n,2) - Σ 每个连通块 C(块大小,2)
void count_unreachable0() {
unreachable0 = (ll)n * (n - 1) / 2;
for (int i = 0; i < n; i++) {
if (find_root(i) != i) continue; // 只在根上统计一次
ll s = dsu[i].sz;
unreachable0 -= s * (s - 1) / 2;
}
}
// 迭代式 Tarjan:求桥 + DFS 树子树大小。同一轮 DFS 里完成,二者和桥一一对应。
void find_bridges() {
int timer = 0;
for (int s = 0; s < n; s++) {
if (ver[s].dfn != 0) continue;
ver[s].dfn = ver[s].low = ++timer;
ver[s].sub = 1;
ver[s].it = head[s];
int top = 0;
dfs_stack[top++] = s;
while (top > 0) {
int u = dfs_stack[top - 1];
int e = ver[u].it;
if (e != -1) {
ver[u].it = arc_nxt[e];
int id = e >> 1;
if (id == ver[u].pe) continue; // 父边跳过:按边编号跳,重边才不会被误判成桥
int v = arc_to[e];
if (ver[v].dfn == 0) {
ver[v].dfn = ver[v].low = ++timer;
ver[v].pe = id;
ver[v].sub = 1;
ver[v].it = head[v];
dfs_stack[top++] = v;
} else if (ver[v].dfn < ver[u].low) {
ver[u].low = ver[v].dfn; // 返祖边(含重边指向祖先的那条)
}
} else {
top--; // u 的出弧走完,回溯到父亲 p
if (top == 0) break;
int p = dfs_stack[top - 1];
ver[p].sub += ver[u].sub;
if (ver[u].low < ver[p].low) ver[p].low = ver[u].low;
// 子树 u 回不到 p 或更高处 → 父边是桥,子树 u 就是被切下来的一侧
if (ver[u].low > ver[p].dfn) bridge_child[ver[u].pe] = u;
}
}
}
}
void answer_queries() {
for (int q = 0; q < Q; q++) {
int x = FastIO::read_int();
ll ans = unreachable0;
int ch = bridge_child[x];
if (ch >= 0) {
ll c = dsu[find_root(ch)].sz; // 该边所在连通块大小
ll s = ver[ch].sub; // 被切下来的子树大小
ans += s * (c - s);
}
FastIO::write_int(ans % 1000);
}
FastIO::flush_out();
}
int main() {
read_input();
count_unreachable0();
find_bridges();
answer_queries();
return 0;
}复杂度
- 时间:并查集
;Tarjan 每条弧恰好被看一次, ; 每次询问 查表并取模, 。总计 。 题面上限为 、 、 , C++ 版在 的两个顶格点上实测 s(限时 1000 ms)。 Python 版在同样的顶格点上实测 s(点 10)与 s(点 9),后者超过 1000 ms 的限时,有 TLE 风险(算法未降级)。 - 空间:
head、dfn、low、sub等按点数开,均为; 链式前向星的弧数组为 ; bridge_child按边数开为。合计 , 顶格约 MB 量级(限时 256 MB)。 - 与 Python 解法的关系:
main.py与main.cpp是同一算法——链式前向星、 带大小的并查集、迭代式 Tarjan 求桥与子树大小、询问时累加。 两版都把桥信息落成一张按边编号索引的表,所以 次询问都是查表。
总结
- 把答案拆成"与删边无关的基线 + 单条边的贡献":
。 这一拆解把 次"删边后重新算连通性"降到 查表。 - 只有桥才改变可达性:删非桥边(环上的边、重边之一、自环)图结构不变,答案就是
。 - 一次 DFS 同时得到桥的集合与切下来的子树大小:
sub[u]天然就是删掉父边后被封住的那一侧, 判据low[u] > dfn[p]与"这侧有多大"是同一个条件的两个面。 - 重边必须按边编号跳过父边,不能按父顶点跳过,否则平行边会被误判成桥;自环始终不是桥。
- 大图要用迭代 DFS:链状数据下递归深度为
,会爆栈;显式栈里保存"当前出弧指针"即可。 - 计数别用
int:与 都能到 量级,C++ 里必须用 long long。
验证记录
- 数据来源:本目录数据由素材仓库的
data.py(cyaron 生成器)配合std.cpp现场生成, 共 10 个测试点,属于自造数据**,不是官方原数据;题面亦可能是依据公开描述重建的, 因此出题意图(尤其是"统计全图不可达点对、而不是只统计被拆开的两侧"这一读法) 以样例为准,本文档的算法按该读法实现。 - 样例:题面唯一的样例输入
4 3 3 / 0 1 / 1 0 / 0 2 / 0 1 2,main.cpp与main.py输出均为3 3 5,与题面输出一致(三组逐行比对全过)。 - 10 个测试点:
main.cpp与main.py逐点跑真实数据并与.out比对,全部一致。 其中点 1/2 是最小边界(的自环、 全森林), 点 8 是 点的链(全桥,答案接近 量级,用来检验子树大小 的计算), 点 9/10 是 同时顶格并专门卡递归爆栈与按父顶点跳边的错解。 - 随机对拍:另写一份每次询问重建并查集的
暴力解作参照,固定种子生成 带重边/自环的小图( )跑 250 组、 偏向树结构的图跑 151 组, main.cpp全部与暴力一致;同一批小图再用main.py跑 501 组,也全部一致。 - 独立复核:素材仓库自带的
std.cpp与本文档算法等价,但本文档两版解法是重新实现的 (链式前向星数组布局、迭代栈写法、按边编号跳父边三处均独立编写),并非照抄; 两版结论与std.cpp在 10 个点上逐点一致。 - 验收工具:
python3 scripts/problem-analysis-tools/accept.py --dry-run 1734通过 (main.cpp真实数据 10 个点全 PASS,main.py10/10)。