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

洛谷1656题解:基于Tarjan算法求解割边问题(附代码与详细步骤)

2个月前 (07-03)

洛谷1656题解:基于Tarjan算法求解割边问题(附代码与详细步骤) 洛谷题解 图论算法 Tarjan算法 C++ 连通分量 第1张

一、题目解读

洛谷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;
}

五、总结

Tarjan算法通过巧妙的时间戳与回边处理,高效识别割边,适用于稀疏图。关键点在于理解low值的含义(最小可到达祖先时间戳),以及割边条件的推导。本文代码简洁,注释清晰,为同类图论问题提供模板参考。建议结合实例调试,加深算法理解。

原创内容 转载请注明出处

分享给朋友:

相关文章

力扣119题:从O(n²)到O(2n):杨辉三角高效空间优化

力扣119题:从O(n²)到O(2n):杨辉三角高效空间优化

题目重解:给定一个非负索引 rowIndex,返回杨辉三角的第 rowIndex 行。不同于生成整个杨辉三角,这道题要求我们只返回特定行,且空间复杂度应尽可能优化。例如输入3,需要返回[1,3,3,1...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

洛谷1111题解题全解析:基于Kruskal算法与并查集的最小生成树实现

洛谷1111题解题全解析:基于Kruskal算法与并查集的最小生成树实现

一、题目解读洛谷1111题是一道经典的图论问题,要求构建一个无向图的最小生成树,并输出其最大边权值。题目核心在于通过给定的边集合,找到连接所有节点的最小权值子集,同时保证无环。这通常涉及最小生成树算法...

牛客14496题解:括号最大深度问题(栈思想与代码优化)

牛客14496题解:括号最大深度问题(栈思想与代码优化)

一、题目解读牛客14496题要求计算给定括号字符串中的最大深度。例如,对于字符串 "(()())",最大深度为2。题目考察对括号嵌套结构的理解,以及如何通过编程找到最深嵌套层次。二...

力扣3112题解法:带时间限制的最短路径问题解析(C++代码)

力扣3112题解法:带时间限制的最短路径问题解析(C++代码)

一、题目解读力扣3112题要求解决带时间限制的最短路径问题:给定一个有向图,节点具有消失时间,需计算从起点到各节点的最短路径,且路径总时间不能超过节点的消失时间。题目难点在于需在传统最短路径算法(如D...

【力扣2846题】图论+二进制提升:高效解决连通性问题(附C++代码)

【力扣2846题】图论+二进制提升:高效解决连通性问题(附C++代码)

一、题目解读力扣2846题要求解决一个基于图连通性的操作优化问题。给定一个无向图,包含边权重,以及一系列查询,每个查询询问两点间路径的最小操作次数。题目关键在于高效计算路径上权重分布的统计信息,并转化...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。