并查集求桥C++代码和暴力法求桥的C++代码

并查集求桥的 C++ 代码：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 100010;

int n, m, cnt, ans;
int fa[MAXN], vis[MAXN], head[MAXN];
struct Edge {
    int to, nxt;
} edge[MAXN << 1];

void add(int u, int v) {
    edge[++cnt].to = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}

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

void merge(int u, int v) {
    int a = find(u), b = find(v);
    if (a != b) fa[a] = b;
}

void dfs(int u, int pre) {
    vis[u] = 1;
    for (int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        if (v == pre) continue;
        if (!vis[v]) {
            dfs(v, u);
            merge(u, v);
        } else {
            if (find(u) != find(v)) ans++;
        }
    }
}

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;
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) dfs(i, 0);
    }
    cout << ans << endl;
    return 0;
}

暴力法求桥的 C++ 代码：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 100010;

int n, m, cnt, ans;
int dfn[MAXN], low[MAXN], vis[MAXN], head[MAXN];
struct Edge {
    int to, nxt;
} edge[MAXN << 1];

void add(int u, int v) {
    edge[++cnt].to = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}

void tarjan(int u, int pre) {
    dfn[u] = low[u] = ++cnt;
    vis[u] = 1;
    for (int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        if (v == pre) continue;
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (dfn[u] < low[v]) ans++;
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) tarjan(i, 0);
    }
    cout << ans << endl;
    return 0;
}