c++代码实现:用并查集解决图论-桥问题,不使用Tarjan算法
时间: 2024-02-18 09:04:05 浏览: 90
以下是使用并查集解决图论-桥问题的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, cnt, ans;
int fa[MAXN], low[MAXN], dfn[MAXN];
vector<int> vec[MAXN];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void Union(int u, int v) {
int x = find(u);
int y = find(v);
if (x != y) fa[x] = y;
}
void tarjan(int u, int pre) {
low[u] = dfn[u] = ++cnt;
for (int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i];
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) {
ans++;
Union(u, v);
}
} else if (v != pre) {
low[u] = min(low[u], dfn[v]);
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
vec[u].push_back(v);
vec[v].push_back(u);
}
tarjan(1, 0);
cout << ans << endl;
return 0;
}
```
其中,`find`函数是并查集中的查找函数,`Union`函数是合并两个集合的函数。
在`tarjan`函数中,`low[u]`表示u能够到达的最小dfn值,`dfn[u]`表示u的dfs序,`pre`表示u的父亲节点。当`v`是`u`的子节点时,如果`v`还没有被访问过,就递归调用`tarjan`函数,并更新`low[u]`的值。如果`low[v] > dfn[u]`,则说明(u, v)是桥,合并u和v所在的集合。如果`v`已经访问过,并且v不是u的父亲节点,就更新`low[u]`的值。
最后输出ans即可,ans表示桥的数量。
注意:此代码实现并不是最优解,仅作为参考。
阅读全文