炸铁路

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

把无向图做一遍 Tarjan，若树边 u-v 满足 low[v] > dfn[u]，说明 v 子树回不到 u 及其祖先，这条边就是桥。

OJ: luogu

题目 ID: P1656

难度:普及+/提高

标签:图论tarjan割边

日期: 2026-06-20 01:41

目录

  1. 题意
    1. 样例图
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给一张无向连通图，要求找出所有满足下面条件的边：

  • 删除这条边后，图会变得不连通

题目把这样的边叫做 key road。

输出所有这样的边，按端点从小到大、再按字典序排序。

样例图

这张图把样例画成无向图：

graph G {
  1 -- 2;
  2 -- 3;
  2 -- 4;
  3 -- 5;
  4 -- 5;
  5 -- 6;
}

从图中可以看到：

  • 删掉 1-2 后，点 1 会被单独隔开
  • 删掉 5-6 后，点 6 会被单独隔开

所以答案是：

1 2

5 6

思路

先看一个最直接的小数据暴力：

cpp
// brute.cpp：依次删边，再重新判断图是否仍然连通。
// 这个做法复杂度较高，只适合小数据理解题意和辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
const int MAXM = 50;

struct Edge {
    int u, v;
} edges[MAXM];

struct EdgeAnswer {
    int u, v;

    bool operator<(const EdgeAnswer &other) const {
        if (u != other.u) {
            return u < other.u;
        }
        return v < other.v;
    }
};

int n, m;
vector<int> g[MAXN];
bool vis[MAXN];
vector<EdgeAnswer> answer;

void dfs(int u) {
    vis[u] = true;
    for (size_t i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!vis[v]) {
            dfs(v);
        }
    }
}

// 删掉第 ban 条边后，检查整张图是否仍然连通。
bool connected_without(int ban) {
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        vis[i] = false;
    }

    for (int i = 1; i <= m; i++) {
        if (i == ban) {
            continue;
        }
        g[edges[i].u].push_back(edges[i].v);
        g[edges[i].v].push_back(edges[i].u);
    }

    dfs(1);

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].u >> edges[i].v;
    }

    for (int i = 1; i <= m; i++) {
        if (!connected_without(i)) {
            int a = edges[i].u;
            int b = edges[i].v;
            if (a > b) {
                swap(a, b);
            }
            answer.push_back({a, b});
        }
    }

    sort(answer.begin(), answer.end());
    for (size_t i = 0; i < answer.size(); i++) {
        cout << answer[i].u << ' ' << answer[i].v << '\n';
    }

    return 0;
}

暴力做法很直观：

  1. 枚举每一条边
  2. 假装把它删掉
  3. 重新做一次 DFS/BFS 看图是否还连通

这个方法好理解，但每删一条边都要重跑一遍搜索，总复杂度太高。

正式做法就是 Tarjan 求桥。

对每个点维护：

  • dfn[u]：点 u 的 DFS 访问次序
  • low[u]：从 u 出发，沿 DFS 树边向下走、再最多走一条返祖边，能回到的最早时间戳

设在 DFS 树里有一条树边 u -> v。

如果：

low[v] > dfn[u]

说明从 v 这棵子树出发，完全没有办法绕路回到 u 或 u 的祖先。 那么一旦删掉边 u-v，v 这整棵子树就和外部断开了，所以它就是桥。

反过来，如果：

low[v] <= dfn[u]

说明 v 子树里至少还能通过某条返祖边绕回去，那么删掉 u-v 后图仍然连通，这条边不是桥。

这类题写代码时还有一个细节：

  • 不要只写 v != fa 来跳过父边

因为无向图里可能有重边。更稳妥的写法是记录“进入当前点的是哪一条边”，遍历时只跳过它的反向边。这样即使两个点之间有多条边，也不会误判桥。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXM = 4005;

struct EdgeAnswer {
    int u, v;

    bool operator<(const EdgeAnswer &other) const {
        if (u != other.u) {
            return u < other.u;
        }
        return v < other.v;
    }
};

int n, m;

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

// Tarjan 求桥时使用的时间戳。
int dfn[MAXN], low[MAXN], dfs_clock;

vector<EdgeAnswer> answer;

void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 由于这里的边编号从 1 开始，所以一对反向边分别是 (1,2)、(3,4) ...
// 这个函数返回某条边对应的反向边编号。
int reverse_edge(int id) {
    if (id & 1) {
        return id + 1;
    }
    return id - 1;
}

// u: 当前点
// in_edge: 进入 u 的那条边的编号
// 不能简单写成 v != fa，因为无向图里可能有重边。
void tarjan(int u, int in_edge) {
    dfn[u] = low[u] = ++dfs_clock;

    for (int i = head[u]; i != 0; i = nxt[i]) {
        int v = to[i];

        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);

            // 如果 v 子树回不到 u 或 u 的祖先，那么 u-v 就是桥。
            if (low[v] > dfn[u]) {
                int a = u;
                int b = v;
                if (a > b) {
                    swap(a, b);
                }
                answer.push_back({a, b});
            }
        }
        else if (i != reverse_edge(in_edge)) {
            // 这里遇到的是返祖边，用祖先的 dfn 更新 low。
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i, -1);
        }
    }

    sort(answer.begin(), answer.end());
    for (size_t i = 0; i < answer.size(); i++) {
        cout << answer[i].u << ' ' << answer[i].v << '\n';
    }

    return 0;
}

复杂度

设点数为 n，边数为 m。

Tarjan 只会把每条边访问常数次，所以：

  • 时间复杂度 O(n+m)O(n+m)
  • 空间复杂度 O(n+m)O(n+m)

总结

这题本质就是桥模板题。真正要记住的是判断式：

low[v] > dfn[u]

它表示 v 子树没有任何后路能回到 u 以上，因此 u-v 就是割边。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析