c++代码实现:用并查集解决图论-桥问题,不使用Tarjan算法

以下是使用并查集解决图论-桥问题的C++代码，不使用Tarjan算法：

#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 dfs(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]) {
            dfs(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);
    }
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

该代码与使用Tarjan算法的代码相似，只是将Tarjan算法中的递归调用改为了深度优先搜索。在`dfs`函数中，`low[u]`表示u能够到达的最小dfn值，`dfn[u]`表示u的dfs序，`pre`表示u的父亲节点。当`v`是`u`的子节点时，如果`v`还没有被访问过，就递归调用`dfs`函数，并更新`low[u]`的值。如果`low[v] > dfn[u]`，则说明(u, v)是桥，合并u和v所在的集合。如果`v`已经访问过，并且v不是u的父亲节点，就更新`low[u]`的值。

最后输出ans即可，ans表示桥的数量。

注意：此代码实现并不是最优解，仅作为参考。