用c++应用并查集编写代码找出一个无向图的所有桥

以下是使用C++编写的应用并查集的代码，用于查找无向图中的所有桥。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> graph[100005]; // 存储无向图的邻接表
int dfn[100005], low[100005]; // dfn和low数组
int timestamp = 0; // 时间戳
bool is_bridge[100005]; // 存储每条边是否为桥
int parent[100005]; // 并查集数组，用于找到桥的两个端点

// 并查集的find操作
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// 并查集的merge操作
void merge(int x, int y) {
    int px = find(x);
    int py = find(y);
    parent[px] = py;
}

// DFS遍历函数
void tarjan(int u, int parent_edge) {
    dfn[u] = low[u] = ++timestamp;
    for (int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if (dfn[v] == 0) { // 如果v未被访问过
            tarjan(v, i);
            low[u] = min(low[u], low[v]); // 更新low值
            if (low[v] > dfn[u]) { // 如果(u,v)是桥
                is_bridge[i] = true;
            } else { // 否则合并u和v所在的连通块
                merge(u, v);
            }
        } else if (i != parent_edge && dfn[v] < dfn[u]) { // 如果v被访问过，且(v,u)不是树边
            low[u] = min(low[u], dfn[v]); // 更新low值
            merge(u, v); // 合并u和v所在的连通块
        }
    }
}

int main() {
    int n, m; // n个点，m条边
    cin >> n >> m;
    for (int i = 1; i <= n; i++) parent[i] = i; // 初始化并查集数组
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    tarjan(1, -1); // 从1开始遍历，parent_edge为-1表示没有父边
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i];
            if (find(u) != find(v) && is_bridge[i]) { // 如果(u,v)是桥且u和v不在同一个连通块中
                cout << u << " " << v << endl; // 输出桥
            }
        }
    }
    return 0;
}

这段代码使用了Tarjan算法和并查集，时间复杂度为O(mα(n))，其中α(n)是阿克曼函数的反函数，可以认为是一个很小的常数。