魔法石

GitHub跳转原题关系图返回列表

tarjan 求割边把图缩成边双与桥树,src→dst 在桥树上的唯一路径里只要有权 1 的桥或内部含权 1 边的边双即 YES。

OJ: roj

题目 ID: 1729

难度:提高+/省选-

标签:图论tarjan割边边双连通分量python

创建: 2026-10-07 19:07

更新: 2026-10-07 19:07

形式化题目

给定无向图 G=(V,E)G=(V,E),∣V∣=n|V| = n、∣E∣=m|E| = m,每条边带权 ce∈{0,1}c_e \in \{0,1\} (ce=1c_e = 1 表示这条桥的桥心有一块魔法石)。给定 src,dst∈Vsrc, dst \in V,问是否存在一条 边不重复的走法(trail)——每条边至多被使用一次——从 srcsrc 出发、终止于 dstdst, 且途中至少经过一条 ce=1c_e = 1 的边。多组数据,每组独立输出 YES / NO。

“石桥走过就崩塌、不能原路返回"正是"每条边至多使用一次”;"收集到魔法石"就是 “用到的边集合里存在 ce=1c_e = 1 的边”。注意允许在同一个岛上反复停留(点可以重复经过), 被限制的只有边。

用连通子图的语言重述一遍:答案 YES 当且仅当存在 S⊆ES \subseteq E,使得

  • SS 的边所关联的顶点连通,且包含 srcsrc 与 dstdst;
  • SS 中奇度顶点的集合恰为 {src,dst}\{src, dst\}(若 src=dstsrc = dst 则要求全部顶点偶度);
  • SS 中存在 ce=1c_e = 1 的边。

前两条正是"SS 存在以 src,dstsrc,dst 为端点的欧拉 trail",与"srcsrc 到 dstdst 的边不重复走法" 一一对应。

正解

思路

第一步:割边 + 边双缩点。 用 tarjan 求出所有割边;把"删掉全部割边后"的每个连通块 缩成一个点,就得到边双连通分量(e-DCC)。割边保留为点与点之间的边,于是原图被压成 一棵"桥树"(若原图不连通则是桥树林)。

第二步:边双内部可以随便顺路取石。 需要一条引理:

在 2-边连通的图中,任意两条边 e,fe, f 一定落在同一条闭 trail 上。

证明:取一条含 ee 的闭 trail WW。若 f∈Wf \in W 已经成立;否则考虑 G−E(W)G - E(W) 中含 ff 的连通块 CC。因为图没有割边,CC 与 WW 之间不可能只靠一条边相连(那条边就会是割边), 所以至少有两条边把 CC 接到 WW 的两个不同顶点 y1,y2y_1, y_2 上。WW 是闭 trail,把 y1y_1 到 y2y_2 的两段弧记为 A1,A2A_1, A_2,ee 必属于其中一段,记作 AA。再把 CC 中一条 y1→y2y_1 \to y_2 且经过 ff 的路径(CC 连通,必存在)接上 AA,就得到同时含 ee 与 ff 的闭 trail。

于是对边双内部的任意"入口 xx、出口 yy"和任意内部边 ee:在边双上补一条虚边 (x,y)(x,y) (x=yx = y 时补自环),新图仍是 2-边连通的,由引理存在同时含 ee 与虚边的闭 trail, 删掉虚边就是一条 x→yx \to y 且经过 ee 的 trail。结论:只要路径经过某块边双,就能 顺便取走这块边双内部的任何一块石头,而不影响进出。

第三步:桥树上只能走唯一路径。 缩点后,src→dstsrc \to dst 的走法在桥树上是 comp(src)→comp(dst)comp(src) \to comp(dst) 的唯一路径 PP:路径之外的桥一旦跨过去,就再没有别的边 能回到路径上(否则它不是割边),所以那些分支里的石头永远取不到。于是

  • 若 comp(src)comp(src) 与 comp(dst)comp(dst) 不在同一棵桥树上(原图不连通),输出 NO;
  • 否则答案 YES   ⟺  \iff PP 上存在 c=1c = 1 的桥,或 PP 上存在内部含 c=1c = 1 边的边双。

第四步:实现。 记 has_art[v] 为边双 vv 内部是否有权 1 的边。在桥树上从 comp(src)comp(src) 出发 BFS/DFS,维护前缀或

acc[v]=acc[u]  ∨  [ w(u,v)=1 ]  ∨  has_art[v],\text{acc}[v] = \text{acc}[u] \;\lor\; [\,w(u,v) = 1\,] \;\lor\; \text{has\_art}[v],

答案就是 acc[comp(dst)](comp(dst)comp(dst) 不可达时输出 NO)。comp(src)=comp(dst)comp(src) = comp(dst) 时 acc\text{acc} 的初值 has_art[comp(src)]\text{has\_art}[comp(src)] 正好是正确答案。

以题面样例为例:第 1 组 {1,2,3}\{1,2,3\}、{4,5,6}\{4,5,6\} 各是一块边双,中间的桥 3−43-4 权为 1 且恰在 1→61 \to 6 的路径上,YES;第 2 组的石在悬挂桥 2−52-5 上,它不在 1→41 \to 4 的 路径上,NO;第 3 组 1..51..5 整体 2-边连通,内部有权 1 的边 4−54-5,YES。

代码

Python 短解法(标准库,迭代 tarjan,与 C++ 同阶):

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 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,防长链爆栈):

cpp
/**
 * 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;
}

复杂度

  • 时间:每组 O(n+m)O(n + m)(tarjan 一次 DFS、并查集近似线性、桥树一次 BFS), 共 O(∑(n+m))O\big(\sum (n + m)\big),最坏 10×(3×105+3×105)10 \times (3 \times 10^5 + 3 \times 10^5) 量级。
  • 空间:O(n+m)O(n + m),链式前向星按 2m2m 条有向边计。

总结

  • 核心是把"桥走过就塌"翻译成"trail(边不重复走法)“,再把图沿割边拆成 边双 + 桥树两层:边双内部是"可以自由绕路"的柔性部分,桥是"只能沿唯一路径走一遍” 的刚性部分,两类石头的判定因此分开。
  • 最容易错的两点:① 把石头在边双内部也当成"必须走割边"处理;② 忘记路径之外的分支 根本回不来(题面样例第 2 组就是这类陷阱,悬挂桥外侧有石却是 NO)。
  • 实现细节:n,m≤3×105n,m \le 3 \times 10^5 且 T≤10T \le 10,链状图会让递归 DFS 爆栈,tarjan 必须 写成显式栈;割边要按边下标(eid ^ 1)跳过父边而不是按端点编号,否则重边会被误判 成割边。
  • 数据说明:本题素材源自带 data.py 生成脚本,data/ 中的 10 个点是自造的 (按等价原题 CF652E 的保证:无自环、无重边、每组图连通),题面文字也是网络重建的, 与官方原题在细节约定上可能有出入,题解按上面的题面表述推导。
  • 本题与 Codeforces 652E《Pursuit For Artifacts》是同一题(人物 Johnny、每条桥只走一次、 边权 0/1、多组数据、n,m≤3×105n,m \le 3 \times 10^5),样例逐组一致(YES / NO / YES), 可用该题的判定准则交叉验证。