Tarjan 边栈求点双:桥即不在任何简单环上的边;块内边数大于点数时块内每条边都在至少两个简单环上,累加这些块的边数。
OJ: roj
题目 ID: 1735
难度:提高
标签:图论点双连通分量Tarjanpython
创建: 2026-10-07 20:26
更新: 2026-10-07 20:26
形式化题目
给定无向图
这里的"简单环"指顶点不重复、边长
所求的两个量彼此不重叠:环数为
正解
思路
两个答案看起来要分别回答"零个环"和"两个以上环",但可以用同一件工具一次算完:Tarjan 的点双连通分量(块)分解。
答案一:
若 low[v] > dfn[u] 逐条数即可。
答案二:逐个点双检查"边数是否大于点数"。
块的分解把一个连通块切成一棵"块-割点树",每个块是极大的 2-连通子图(或一条桥)。关键性质是:
-
同一个块内的任意两条边同属于某个简单环。 这是 2-连通图的经典结论(等价说法是"过任意两条边都有简单回路",可由耳分解或 Menger 定理推出):在 2-连通图里对任意两条边各取一个端点,两个端点之间都有两条内部不相交的道路,拼起来就是过一个端点所在边与另一条边的简单环。
-
设块
有 个顶点、 条边。单条桥的块满足 ; 的块是 2-连通的,度数之和 给出 。于是非桥的块只有两种情形: :由 得每点度数恰为 , 就是一个简单环,此时任何简单环都必须用上全部 条边(每个点度数已用尽),故块内每条边恰在 1 个简单环上; :反设某条边 只在一个简单环 上。因为 ( 是块内的环,长度不超过 ),块内必有边 。由性质 1,存在同时包含 与 的简单环 ; 迫使 ,于是 落在两个不同简单环上,矛盾。所以每条边至少在两个简单环上。
换句话说,
意味着这个块"环太多",块内每条边都进 。 小例子:
个点的环本身只有一条简单环可走,每条边恰在 1 个环上;一旦加一条弦( ),每条边立刻多出第二条环。例如四边形 0-1-2-3-0加上弦后,边 既在 0-1-2-0上,也在0-1-2-3-0上。
于是算法的形状就定下来了:跑一遍 Tarjan,同时完成两件事——用 low[v] > dfn[u] 数桥得到
块内点数为什么必须去重? 边栈弹出的是块内边,同一条边的两个端点会多次出现(std::set(原题内存只有 32MB 时这点很关键)。
实现细节。 (顶点, 出边游标, 入边编号),弹出时才算这一层的收尾。边的存储把无向边 2i / 2i+1,Python 同样用 2i / 2i+1),于是 0;Python 里弧号从 -1(因为 -1 ^ 1 = -2 也不是合法弧号)。
块的弹出时机是固定的:low[u] >= dfn[p],就说明 low[u] > dfn[p])、这个块的
代码
#!/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:26
# update_at: 2026-10-07 20:26
import sys
# 边弧编号约定:无向边 i 拆成弧 2i(u->v)与 2i+1(v->u),于是 e ^ 1 恒为反向弧,
# 「跳过父边」只要比较 e == (fe ^ 1);根的 fe 用 -1,因为 -1 ^ 1 = -2 不是合法弧号。
type Adj = list[list[int]] # adj[u] = 从 u 出发的弧编号列表
def count_edges(n: int, adj: Adj, arc_to: list[int]) -> tuple[int, int]:
"""Tarjan 点双;返回 (桥数, 落在「边数 > 点数」块内的边数)。
桥 = 不在任何简单环上的边(low[u] > dfn[父]);块内边数 > 点数时块必含
>= 2 个环且每条边都至少属于两个简单环,把这些块的边数累加即为第二个答案。
"""
dfn = [0] * n
low = [0] * n
vmark = [0] * n # 统计块内点数的去重标记:值等于当前块号表示本块内已数过
estack: list[int] = [] # 边栈:每弹空一次得到一个点双
fu = [0] * n # 迭代 dfs 的帧:当前点
fptr = [0] * n # 帧内游标:已处理到邻接表第几条弧
ffe = [-1] * n # 帧的入边编号,-1 表示该帧是根(无父边)
ans1 = ans2 = 0
timer = 0
blk = 0
for s in range(n):
if dfn[s]:
continue
timer += 1
dfn[s] = low[s] = timer
top = 0
fu[0], fptr[0], ffe[0] = s, 0, -1
while top >= 0: # 显式栈 dfs:深链可达 1e4,不用递归
u = fu[top]
arcs = adj[u]
pos = fptr[top]
if pos < len(arcs):
fptr[top] = pos + 1
e = arcs[pos]
is_parent_arc = e == (ffe[top] ^ 1) # 用弧号判父边:反向弧恒为 e ^ 1
if is_parent_arc:
continue
v = arc_to[e]
if dfn[v] == 0: # 树边:入栈后进入 v
estack.append(e)
timer += 1
dfn[v] = low[v] = timer
top += 1
fu[top], fptr[top], ffe[top] = v, 0, e
elif dfn[v] < dfn[u]: # 回边:只从较深的一端入栈一次
estack.append(e)
if dfn[v] < low[u]:
low[u] = dfn[v]
else:
fe = ffe[top]
top -= 1 # u 的邻接表走完,弹出 u
if fe < 0: # 根:它的块已由子节点返回时全部弹空
continue
parent = fu[top]
if low[u] < low[parent]:
low[parent] = low[u]
if low[u] >= dfn[parent]: # 找到一个点双,它含父边 fe
if low[u] > dfn[parent]:
ans1 += 1 # 父边是桥
blk += 1
ecnt = vcnt = 0
while True:
e = estack.pop()
ecnt += 1
a, b = arc_to[e ^ 1], arc_to[e] # e 的起点、终点
if vmark[a] != blk:
vmark[a] = blk
vcnt += 1
if vmark[b] != blk:
vmark[b] = blk
vcnt += 1
if e == fe:
break
if ecnt > vcnt:
ans2 += ecnt
return ans1, ans2
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
while True:
n, m = next(data), next(data)
if n == 0 and m == 0: # 输入结束
break
arc_to = [0] * (2 * m)
adj: Adj = [[] for _ in range(n)]
for i in range(m):
u, v = next(data), next(data)
arc_to[2 * i], arc_to[2 * i + 1] = v, u
adj[u].append(2 * i)
adj[v].append(2 * i + 1)
ans1, ans2 = count_edges(n, adj, arc_to)
out.append(f"{ans1} {ans2}")
print("\n".join(out))
if __name__ == "__main__":
solve()/**
* 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:26
* update_at: 2026-10-07 20:26
*/
// 环上计数:多组数据,每组求
// ans1 = 不在任何简单环上的边数(= 桥数)
// ans2 = 在至少两个简单环上的边数(= 「边数 > 点数」的点双连通分量里的边数之和)
// 读到 0 0 结束。n <= 1e4,m <= 1e5,点从 0 开始编号。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005; // 点数上限 1e4,留一点余量
const int MAXM = 200005; // 无向边存成两条有向边:2 * 1e5
typedef long long ll;
// 链式前向星。边从 2 开始编号,于是 e 与 e ^ 1 互为反向边,
// 「跳过父边」只要比较 e == (fe ^ 1),不用额外存每条边的起点。
int head[MAXN]; // head[u]:点 u 的第一条出边
int eto[MAXM]; // eto[e]:边 e 的终点
int enxt[MAXM]; // enxt[e]:与 e 同起点的下一条边
int edge_cnt;
int dfn[MAXN]; // dfn[u]:u 的 dfs 序,0 表示未访问
int low[MAXN]; // low[u]:u 的子树能通过回边到达的最小 dfn
int vstamp[MAXN]; // 统计块内点数用的时间戳:等于当前块号表示本块内已数过
int estack[MAXM]; // 边栈:每次弹栈结束就得到一个点双(块)
int estop;
ll ans1, ans2; // 一组数据的两个答案
// 迭代 dfs 的一帧。深链可长达 1e4,递归写法有爆栈风险,故用显式栈。
struct Frame {
int u; // 当前点
int it; // 正在处理的出边编号,0 表示邻接表已走完
int fe; // 进入 u 的树边编号,0 表示 u 是本次 dfs 的根
};
Frame fstk[MAXN];
// 读入一组数据:n 个点、m 条边,并重置本组用到的全局数组
void read_graph(int n, int m) {
edge_cnt = 2; // 边编号从 2 开始,0 和 1 留给「空边」
for (int i = 0; i < n; i++) {
head[i] = 0;
dfn[i] = 0;
low[i] = 0;
vstamp[i] = 0; // 块号从 1 开始,0 天然表示「还没在块里出现过」
}
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
eto[edge_cnt] = v;
enxt[edge_cnt] = head[u];
head[u] = edge_cnt++;
eto[edge_cnt] = u;
enxt[edge_cnt] = head[v];
head[v] = edge_cnt++;
}
}
// 弹边栈直到弹出入边 pe,得到一个点双。返回块内边数,点数由调用方用块号去重统计。
// 块内边数与点数决定了这个块的性质:边数 > 点数时块内每条边都在至少两个简单环上。
int pop_block(int pe, int blk_id) {
int ecnt = 0;
int vcnt = 0;
while (true) {
int e = estack[estop--];
ecnt++;
int a = eto[e ^ 1]; // 边 e 的起点 = 反向边的终点
int b = eto[e]; // 边 e 的终点
if (vstamp[a] != blk_id) {
vstamp[a] = blk_id;
vcnt++;
}
if (vstamp[b] != blk_id) {
vstamp[b] = blk_id;
vcnt++;
}
if (e == pe) break; // 回到入边,本块弹完
}
return ecnt > vcnt ? ecnt : 0; // 边数 <= 点数时该块不贡献 ans2
}
// 从点 s 出发迭代 dfs,求以它所在连通块里所有点双
void dfs_from(int s, int &timer, int &blk_id) {
dfn[s] = low[s] = ++timer;
int top = 0;
fstk[0].u = s;
fstk[0].it = head[s];
fstk[0].fe = 0;
while (top >= 0) {
int u = fstk[top].u;
int it = fstk[top].it;
if (it != 0) {
fstk[top].it = enxt[it]; // 先推进游标,后面可以自由访问栈
if (it == (fstk[top].fe ^ 1)) continue; // 是父边的反向边,跳过
int v = eto[it];
if (dfn[v] == 0) {
estack[++estop] = it; // 树边入栈
dfn[v] = low[v] = ++timer;
top++;
fstk[top].u = v;
fstk[top].it = head[v];
fstk[top].fe = it;
} else if (dfn[v] < dfn[u]) {
estack[++estop] = it; // 回边:只从较深的一端入栈一次
low[u] = min(low[u], dfn[v]);
}
} else {
int fe = fstk[top].fe;
top--; // 弹出 u
if (fe == 0) continue; // 根节点,其块已在子节点返回时全部弹完
int p = fstk[top].u;
low[p] = min(low[p], low[u]);
if (low[u] >= dfn[p]) {
if (low[u] > dfn[p]) ans1++; // 割边:不在任何简单环上
blk_id++;
ans2 += pop_block(fe, blk_id);
}
}
}
}
// 处理一组数据并输出一行答案
void solve_group(int n, int m) {
read_graph(n, m);
ans1 = 0;
ans2 = 0;
estop = 0;
int timer = 0;
int blk_id = 0;
// 孤立点不构成块,但它的 head 为 0,dfs 进来也只会立刻弹出,无需特判
for (int s = 0; s < n; s++) {
if (dfn[s] == 0) dfs_from(s, timer, blk_id);
}
cout << ans1 << ' ' << ans2 << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
while (cin >> n >> m) {
if (n == 0 && m == 0) break; // 结束标志
solve_group(n, m);
}
return 0;
}复杂度
每组数据时间
总结
本题的落点是"边的环计数"与"块结构"之间的对应关系:
| 边所在的简单环数 | 图结构判据 | 计入 |
|---|---|---|
| 0 | 桥(low[v] > dfn[u]) |
|
| 1 | 所在的块满足 |
不计 |
| 所在的块满足 |
三个量互相补充:一个块要么是桥(
容易写错的三个点:一是块内点数必须去重(用块号时间戳最省内存,不必开 set);二是跳过父边要用弧编号异或而不是"顶点等于父点"(前者在带重边的一般图上同样正确,而且实现更简单);三是深层图要用迭代栈而不是递归。
备注
素材源 new_ROJ/problems/1735/ 里带有数据生成脚本(data.py)与标程(std.cpp),说明本目录的 data/ 是自造的,题面也可能来自网络重建,出题意图与官方原题可能有偏差。经实跑核对,标程算法与上面的推导一致(边栈点双 + 边数大于点数的块累加),本目录的 C++ 与 Python 解法在全部 10 个测试点上输出与 data/*.out 逐字节一致;另用枚举全部简单环的暴力解在 data/ 不含官方数据,不能等同于官方 AC。