当前位置：首页 > 洛谷 > 洛谷1656题解：基于Tarjan算法求解割边问题（附代码与详细步骤）

洛谷1656题解：基于Tarjan算法求解割边问题（附代码与详细步骤）

10个月前 (07-03)

一、题目解读

洛谷1656题要求在无向图中找出所有割边（即删除后导致图不连通的边）。题目核心在于判断图的连通性，并识别哪些边是“桥”。需理解图论中的连通分量概念，以及如何通过算法高效定位割边。

二、解题思路：Tarjan算法原理

采用经典的Tarjan算法求解割边。核心思想：

1. 通过深度优先搜索（DFS）遍历图，记录每个节点的时间戳（dfn）和最小可到达祖先时间戳（low）。

2. 若节点u的子节点v满足low[v] > dfn[u]，则(u,v)为割边（即v及其子树无法通过其他路径回到u访问前的节点）。

3. 利用回边（反向边）更新low值，避免重复计算。

三、解题步骤

1. 建图：使用邻接表G存储无向图，读入n个节点和m条边，双向添加边(a,b)和(b,a)。

2. 初始化：时间戳timestamp置0，dfn和low数组清零。

3. 执行Tarjan算法：

○ 对每个未访问节点i，调用tarjan(i, -1)，递归处理子树。

○ 递归中更新dfn和low，并判断割边条件。

4. 结果处理：将割边存入bridges（按节点值排序），最终输出。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 155;  
vector<int> G[MAXN];  // 邻接表存图
int dfn[MAXN], low[MAXN];
int timestamp = 0;     // 时间戳
vector<pair<int, int>> bridges; // 存储所有割边

// Tarjan核心函数，u为当前节点，father为父节点
void tarjan(int u, int father) {
    dfn[u] = low[u] = ++timestamp;  // 初始化dfn和low
    for (int v : G[u]) {            // 遍历u的所有邻接点
        if (!dfn[v]) {              // 未访问过的节点
            tarjan(v, u);           // 递归处理子节点
            low[u] = min(low[u], low[v]);  // 更新low值
            // 割边判断条件：子树无法通过回边到达u的祖先
            if (low[v] > dfn[u]) {
                bridges.push_back({min(u,v), max(u,v)});  
            }
        } else if (v!= father) {     // 处理回边（非父节点）
            low[u] = min(low[u], dfn[v]);  // 更新low值
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int a, b; cin >> a >> b;
        G[a].push_back(b);   // 双向建边
        G[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) tarjan(i, -1);  // 遍历所有连通分量
    }
    sort(bridges.begin(), bridges.end());  // 按字典序排序
    for (auto &p : bridges) {
        cout << p.first << " " << p.second << endl;
    }
    return 0;
}