tarjan 求割边把图缩成边双与桥树,src→dst 在桥树上的唯一路径里只要有权 1 的桥或内部含权 1 边的边双即 YES。
OJ: roj
题目 ID: 1729
难度:提高+/省选-
标签:图论tarjan割边边双连通分量python
创建: 2026-10-07 19:07
更新: 2026-10-07 19:07
形式化题目
给定无向图 YES / NO。
“石桥走过就崩塌、不能原路返回"正是"每条边至多使用一次”;"收集到魔法石"就是
“用到的边集合里存在
用连通子图的语言重述一遍:答案 YES 当且仅当存在
的边所关联的顶点连通,且包含 与 ; 中奇度顶点的集合恰为 (若 则要求全部顶点偶度); 中存在 的边。
前两条正是"
正解
思路
第一步:割边 + 边双缩点。 用 tarjan 求出所有割边;把"删掉全部割边后"的每个连通块 缩成一个点,就得到边双连通分量(e-DCC)。割边保留为点与点之间的边,于是原图被压成 一棵"桥树"(若原图不连通则是桥树林)。
第二步:边双内部可以随便顺路取石。 需要一条引理:
在 2-边连通的图中,任意两条边
一定落在同一条闭 trail 上。
证明:取一条含
于是对边双内部的任意"入口
第三步:桥树上只能走唯一路径。 缩点后,
- 若
与 不在同一棵桥树上(原图不连通),输出 NO; - 否则答案
YES上存在 的桥,或 上存在内部含 边的边双。
第四步:实现。 记 has_art[v] 为边双
答案就是 acc[comp(dst)](NO)。
以题面样例为例:第 1 组 YES;第 2 组的石在悬挂桥 NO;第 3 组 YES。
代码
Python 短解法(标准库,迭代 tarjan,与 C++ 同阶):
#!/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 19:06
# update_at: 2026-10-07 19:06
import sys
from collections.abc import Iterator
NONE = -1 # 链式前向星里"没有下一条边"的哨兵
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Adj = list[int] # 链式前向星的 head / nxt / to / wt 表
type Tree = list[list[tuple[int, int]]] # 桥树邻接表:(边双编号, 桥的权) 列表的列表
def ints(raw: bytes) -> Iterator[int]:
"""顺序产出输入里的整数;比 split() 省内存(本题单组可达 3e5 行、Σm 达 3e6)。"""
num = 0
in_num = False
for b in raw:
if b > 32:
num = num * 10 + b - 48
in_num = True
elif in_num:
yield num
num = 0
in_num = False
if in_num:
yield num
def bridges(n: int, head: Adj, nxt: Adj, to: Adj) -> bytearray:
"""回答"每条有向边是不是割边的某一侧":tarjan 显式栈迭代,避免长链爆栈。"""
dfn = [0] * (n + 1)
low = [0] * (n + 1)
it_e = [0] * (n + 1) # 迭代 DFS 中当前扫到的出边
par_e = [-1] * (n + 1) # 结点在 DFS 树中的入边下标
is_br = bytearray(len(to)) # 成对下标的反向边同时置 1
timer = 0
for root in range(1, n + 1):
if dfn[root]:
continue
timer += 1
dfn[root] = low[root] = timer
it_e[root] = head[root]
par_e[root] = NONE
stack = [root]
while stack:
u = stack[-1]
e = it_e[u]
if e != NONE:
it_e[u] = nxt[e]
parent_back = par_e[u] != NONE and e == (par_e[u] ^ 1)
if parent_back:
continue # 不走父边的反向边(重边才需要靠边下标区分)
v = to[e]
if not dfn[v]: # 树边:继续深搜
par_e[v] = e
it_e[v] = head[v]
timer += 1
dfn[v] = low[v] = timer
stack.append(v)
elif dfn[v] < low[u]: # 返祖边:用 dfn 更新 low
low[u] = dfn[v]
else:
stack.pop() # u 出栈,把 low 回传给父亲
pe = par_e[u]
if pe != NONE:
p = to[pe ^ 1]
if low[u] < low[p]:
low[p] = low[u]
if low[u] > dfn[p]: # (p,u) 是割边
is_br[pe] = is_br[pe ^ 1] = 1
return is_br
def shrink(n: int, m: int, to: Adj, wt: Adj, is_br: bytearray) -> tuple[list[int], list[bool]]:
"""非割边连通块缩成边双:返回 comp(结点 -> 边双编号)与 has_art(边双内部是否有权 1 边)。"""
fa = list(range(n + 1))
size = [1] * (n + 1)
def root(x: int) -> int:
while fa[x] != x:
fa[x] = fa[fa[x]] # 路径折半压缩
x = fa[x]
return x
for e in range(0, 2 * m, 2):
if not is_br[e]:
a, b = root(to[e]), root(to[e ^ 1])
if a != b:
if size[a] < size[b]:
a, b = b, a
fa[b] = a
size[a] += size[b]
comp = [root(v) for v in range(n + 1)]
has_art = [False] * (n + 1)
for e in range(0, 2 * m, 2):
if not is_br[e] and wt[e]:
has_art[comp[to[e]]] = True # 这块边双内部有魔法石,路过就能取
return comp, has_art
def can_collect(cs: int, cd: int, tree: Tree, has_art: list[bool]) -> bool:
"""桥树上 cs -> cd 的唯一路径上,是否经过权 1 的桥或内部有石的边双。"""
acc = {cs: has_art[cs]} # 前缀或:从 cs 走到该边双时能否已取到石
stack = [cs]
while stack and cd not in acc:
u = stack.pop()
for v, w in tree[u]:
if v in acc:
continue
acc[v] = acc[u] or w == 1 or has_art[v]
stack.append(v)
return acc.get(cd, False) # cd 不在同一连通块时为 False
def solve_case(data: Iterator[int]) -> str:
"""读入一组数据,返回该组的 YES / NO。"""
n, m = next(data), next(data)
head = [NONE] * (n + 1)
nxt = [NONE] * (2 * m)
to = [0] * (2 * m)
wt = [0] * (2 * m)
for e in range(0, 2 * m, 2): # 边成对加入,e ^ 1 是反向边
x, y, c = next(data), next(data), next(data)
to[e], wt[e], nxt[e], head[x] = y, c, head[x], e
to[e + 1], wt[e + 1], nxt[e + 1], head[y] = x, c, head[y], e + 1
is_br = bridges(n, head, nxt, to)
comp, has_art = shrink(n, m, to, wt, is_br)
tree: Tree = [[] for _ in range(n + 1)] # 桥树的边就是原图的割边
for e in range(0, 2 * m, 2):
if is_br[e]:
u, v = comp[to[e]], comp[to[e ^ 1]]
tree[u].append((v, wt[e]))
tree[v].append((u, wt[e]))
src, dst = next(data), next(data)
return "YES" if can_collect(comp[src], comp[dst], tree, has_art) else "NO"
def solve() -> None:
data = ints(sys.stdin.buffer.read())
T = next(data)
print("\n".join(solve_case(data) for _ in range(T)))
if __name__ == "__main__":
solve()C++17 正解(fread 快读 + 显式栈 tarjan,防长链爆栈):
/**
* 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 19:06
* update_at: 2026-10-07 19:06
*/
// ROJ 1729《魔法石》
// 题意:n 个岛、m 条无向石桥(走过即崩塌,每条边至多走一次),c=1 表示桥心有魔法石。
// 问是否存在一条 src → dst 的「边不重复的走法(trail)」,途中经过至少一条 c=1 的边。
// 等价原题:Codeforces 652E Pursuit For Artifacts(人物 Johnny、边权 0/1、多组数据)。
//
// 判定准则:tarjan 求割边 → 非割边连通块缩成边双(e-DCC) → 得到「桥树」;
// 设 P 为桥树上 comp[src] → comp[dst] 的唯一路径(不可达即 NO),则
// 答案 = YES ⇔ P 上存在权 1 的桥,或 P 上某个边双内部存在权 1 的边。
// 理由:边双是 2-边连通的,任意两条边落在同一条闭 trail 上(把入口→出口连一条虚边后
// 用「闭 trail 内任意两条边可用耳朵分解拼起来」的结论),所以边双内部可以顺路取石;
// 而割边必须沿 P 的方向各走一次,绕到 P 之外的分支就再也回不来(那条边是桥)。
//
// 实现要点:n,m ≤ 3e5 且 T ≤ 10,长链会爆递归栈 → tarjan 写成显式栈的迭代版;
// Σm 可达 3e6 → 手写 fread 快读 + 输出缓冲;割边按「边下标」跳过父边(eid^1),
// 重边与自环都不会被误判;每组 O(n+m),全局数组按下标覆盖复用。
//
// 数据说明:素材源自带 data.py 生成脚本,data/ 是自造的(按 CF652E 的保证:无自环、
// 无重边、每组图连通),题面亦为网络重建,与官方原题细节可能略有出入。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 300005; // 岛数上限
const int MAXM = 300005; // 桥数上限
int n, m; // 本组数据的岛数、桥数
// 链式前向星存原图,边成对加入,eid^1 是反向边
int head[MAXN];
int eto[2 * MAXM];
int enxt[2 * MAXM];
int ewt[2 * MAXM];
int ecnt;
int dfn[MAXN]; // tarjan 时间戳
int low[MAXN];
int itE[MAXN]; // 迭代 DFS 中当前扫到的出边
int parE[MAXN]; // 结点在 DFS 树中的入边下标
bool isBr[2 * MAXM]; // 该有向边是否为割边的某一侧
int fa[MAXN]; // 并查集:把非割边连成的边双缩点
int sz[MAXN];
int comp[MAXN]; // 结点所属边双的根
bool hasArt[MAXN]; // 边双内部是否存在权 1 的边
// 桥树的链式前向星
int thead[MAXN];
int tto[2 * MAXM];
int tnxt[2 * MAXM];
int twt[2 * MAXM];
int tcnt;
int stk[MAXN]; // 迭代 tarjan 的栈
int que[MAXN]; // 桥树上 BFS 的队列
bool vis[MAXN];
bool acc[MAXN]; // 桥树上从 comp[src] 一路走来的「是否已能取到石」前缀或
char inBuf[1 << 22]; // 输入缓冲(每组最多 3e5 行,用 fread 比 cin 稳)
int inLen = 0, inPos = 0;
char outBuf[1 << 16]; // 输出缓冲
int outPos = 0;
// ---------- 快读 / 快写 ----------
int readInt() {
if (inPos == inLen) {
inLen = (int)fread(inBuf, 1, sizeof(inBuf), stdin);
inPos = 0;
if (inLen == 0) return -1;
}
while (inPos < inLen && (inBuf[inPos] < '0' || inBuf[inPos] > '9')) {
if (++inPos == inLen) {
inLen = (int)fread(inBuf, 1, sizeof(inBuf), stdin);
inPos = 0;
if (inLen == 0) return -1;
}
}
int x = 0;
while (inPos < inLen && inBuf[inPos] >= '0' && inBuf[inPos] <= '9') {
x = x * 10 + (inBuf[inPos] - '0');
if (++inPos == inLen) {
inLen = (int)fread(inBuf, 1, sizeof(inBuf), stdin);
inPos = 0;
if (inLen == 0) break;
}
}
return x;
}
void outStr(const char *s, int len) {
if (outPos + len > (int)sizeof(outBuf)) {
fwrite(outBuf, 1, outPos, stdout);
outPos = 0;
}
for (int i = 0; i < len; ++i) outBuf[outPos++] = s[i];
}
void addEdge(int u, int v, int w) {
eto[ecnt] = v; ewt[ecnt] = w; enxt[ecnt] = head[u]; head[u] = ecnt++;
}
void addTreeEdge(int u, int v, int w) {
tto[tcnt] = v; twt[tcnt] = w; tnxt[tcnt] = thead[u]; thead[u] = tcnt++;
}
int findRoot(int x) {
int r = x;
while (fa[r] != r) r = fa[r];
while (fa[x] != r) { // 路径压缩
int nx = fa[x];
fa[x] = r;
x = nx;
}
return r;
}
void unite(int a, int b) {
a = findRoot(a); b = findRoot(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b); // 按大小合并
fa[b] = a; sz[a] += sz[b];
}
void solve() {
int T = readInt();
if (T < 0) T = 0;
while (T--) {
n = readInt(); m = readInt();
if (n < 1) n = 1;
if (m < 0) m = 0;
// 只清本次用到的范围,避免 T 组间反复 O(MAXN) 清空
for (int i = 1; i <= n; ++i) {
head[i] = -1;
thead[i] = -1;
dfn[i] = 0;
parE[i] = -1;
fa[i] = i;
sz[i] = 1;
hasArt[i] = false;
vis[i] = false;
acc[i] = false;
}
ecnt = 0; tcnt = 0;
for (int i = 0; i < m; ++i) {
int x = readInt(), y = readInt(), c = readInt();
addEdge(x, y, c);
addEdge(y, x, c);
}
for (int i = 0; i < ecnt; ++i) isBr[i] = false;
// ---------- 迭代式 tarjan 求割边(按边下标跳过父边,重边/自环安全) ----------
int timer = 0;
for (int root = 1; root <= n; ++root) {
if (dfn[root]) continue;
int top = 0;
stk[top++] = root;
dfn[root] = low[root] = ++timer;
itE[root] = head[root];
parE[root] = -1;
while (top > 0) {
int u = stk[top - 1];
int e = itE[u];
if (e != -1) {
itE[u] = enxt[e];
if (parE[u] != -1 && e == (parE[u] ^ 1)) continue; // 不走父边的反向边
int v = eto[e];
if (!dfn[v]) { // 树边,压栈继续深搜
parE[v] = e;
itE[v] = head[v];
dfn[v] = low[v] = ++timer;
stk[top++] = v;
} else if (dfn[v] < low[u]) { // 返祖边,用 dfn 更新 low
low[u] = dfn[v];
}
} else {
--top; // u 出栈,把 low 回传给父亲
int pe = parE[u];
if (pe != -1) {
int p = eto[pe ^ 1];
if (low[u] < low[p]) low[p] = low[u];
if (low[u] > dfn[p]) { // (p,u) 是割边
isBr[pe] = true;
isBr[pe ^ 1] = true;
}
}
}
}
}
// ---------- 非割边连通块 = 边双,并查集缩点 ----------
for (int e = 0; e < ecnt; e += 2) {
if (!isBr[e]) unite(eto[e], eto[e ^ 1]);
}
for (int v = 1; v <= n; ++v) comp[v] = findRoot(v);
for (int e = 0; e < ecnt; e += 2) {
if (!isBr[e]) {
if (ewt[e]) hasArt[comp[eto[e]]] = true; // 边双内部的魔法石
} else {
addTreeEdge(comp[eto[e]], comp[eto[e ^ 1]], ewt[e]); // 桥 = 桥树的边
addTreeEdge(comp[eto[e ^ 1]], comp[eto[e]], ewt[e]);
}
}
int src = readInt(), dst = readInt();
int cs = comp[src], cd = comp[dst];
// ---------- 桥树上从 comp[src] 广搜,累积「路上能否取到石」 ----------
int qh = 0, qt = 0;
que[qt++] = cs;
vis[cs] = true;
acc[cs] = hasArt[cs];
while (qh < qt) {
int u = que[qh++];
for (int e = thead[u]; e != -1; e = tnxt[e]) {
int v = tto[e];
if (vis[v]) continue;
vis[v] = true;
acc[v] = acc[u] || twt[e] || hasArt[v]; // 前缀或:桥权 1 或边双内部有石
que[qt++] = v;
}
}
// cs == cd 时 acc[cd] 就是「该边双内部是否有石」,同样成立
if (vis[cd] && acc[cd]) outStr("YES\n", 4);
else outStr("NO\n", 3);
}
if (outPos) fwrite(outBuf, 1, outPos, stdout);
}
int main() {
solve();
return 0;
}复杂度
- 时间:每组
(tarjan 一次 DFS、并查集近似线性、桥树一次 BFS), 共 ,最坏 量级。 - 空间:
,链式前向星按 条有向边计。
总结
- 核心是把"桥走过就塌"翻译成"trail(边不重复走法)“,再把图沿割边拆成 边双 + 桥树两层:边双内部是"可以自由绕路"的柔性部分,桥是"只能沿唯一路径走一遍” 的刚性部分,两类石头的判定因此分开。
- 最容易错的两点:① 把石头在边双内部也当成"必须走割边"处理;② 忘记路径之外的分支
根本回不来(题面样例第 2 组就是这类陷阱,悬挂桥外侧有石却是
NO)。 - 实现细节:
且 ,链状图会让递归 DFS 爆栈,tarjan 必须 写成显式栈;割边要按边下标( eid ^ 1)跳过父边而不是按端点编号,否则重边会被误判 成割边。 - 数据说明:本题素材源自带
data.py生成脚本,data/中的 10 个点是自造的 (按等价原题 CF652E 的保证:无自环、无重边、每组图连通),题面文字也是网络重建的, 与官方原题在细节约定上可能有出入,题解按上面的题面表述推导。 - 本题与 Codeforces 652E《Pursuit For Artifacts》是同一题(人物 Johnny、每条桥只走一次、
边权 0/1、多组数据、
),样例逐组一致( YES / NO / YES), 可用该题的判定准则交叉验证。