c++使用并查集和生成树找无向图中的桥

下面是使用 C++ 实现使用并查集和生成树找到无向图中的桥的代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

int n, m, tot, cnt;
int head[MAXN], dfn[MAXN], low[MAXN], fa[MAXN], id[MAXN], ans[MAXN];
bool vis[MAXN];

struct Edge {
    int to, nxt;
} e[MAXN << 1], tree[MAXN << 1];

void addEdge(int u, int v) {
    e[++tot].to = v;
    e[tot].nxt = head[u];
    head[u] = tot;
}

int find(int x) {
    if (x == fa[x]) {
        return x;
    }
    return fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        fa[fx] = fy;
    }
}

void dfs(int u, int p) {
    dfn[u] = low[u] = ++tot;
    vis[u] = true;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == p) {
            continue;
        }
        if (!dfn[v]) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                ans[++cnt] = i;
            } else {
                merge(u, v);
            }
        } else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    vis[u] = false;
}

void buildTree() {
    for (int i = 1; i <= m; i++) {
        int u = e[i].to, v = e[i ^ 1].to;
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            tree[++tot].to = u;
            tree[tot].nxt = id[fv];
            id[fv] = tot;
            tree[++tot].to = v;
            tree[tot].nxt = id[fu];
            id[fu] = tot;
            fa[fu] = fv;
        }
    }
}

void dfs2(int u, int p) {
    dfn[u] = ++tot;
    for (int i = id[u]; i; i = tree[i].nxt) {
        int v = tree[i].to;
        if (v == p) {
            continue;
        }
        dfs2(v, u);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    dfs(1, 0);
    tot = 0;
    buildTree();
    tot = 0;
    dfs2(1, 0);
    printf("Bridges:\n");
    for (int i = 1; i <= cnt; i++) {
        int u = e[ans[i]].to, v = e[ans[i] ^ 1].to;
        if (dfn[u] > dfn[v]) {
            swap(u, v);
        }
        printf("%d %d\n", u, v);
    }
    return 0;
}

在这个代码中，我们首先使用 DFS 遍历来查找桥。具体来说，我们记录了每个节点的 dfn 和 low 值，同时使用 vis 数组来判断一个节点是否已经被访问过。如果一个节点的 low 值大于其子节点的 dfn 值，则说明该节点与子节点之间的边是桥。否则，我们将该节点与子节点合并到同一个连通块中。

然后，我们使用并查集来构建生成树，并使用 DFS 遍历生成树来记录每个节点的 dfn 值。最后，我们遍历所有的桥，对于每一条桥 $(u, v)$，我们判断其在生成树上的 dfs 序，如果 $dfn_u < dfn_v$，则输出 $(u, v)$；否则，输出 $(v, u)$。

需要注意的是，这个算法的时间复杂度为 $O(m \log n)$，其中 $m$ 为边数，$n$ 为节点数。