【并查集缩点+tarjan无向图求桥】Where are you @牛客练习赛32 D

这道题是一个比较典型的无向图缩点和求桥的问题。

首先我们需要使用 Tarjan 算法求出无向图中的桥，即割边，这里就不再赘述了。

接下来我们需要对图进行缩点操作。具体地，我们使用并查集来维护每个点所属的连通块，然后对于每个连通块进行缩点。这里需要注意的是，在缩点之后，我们需要重新遍历一遍无向图，把所有的桥重新连接起来。

最后，我们只需要对缩点后的无向图中的每个连通块进行 DFS，统计每个连通块内部的边数和连通块间的桥的数量即可。

代码如下：

相关问题

请用C++使用基准法+并查集+DFS除环方法解决无向图求桥的问题

好的，以下是使用C++实现基准法+并查集+DFS除环方法来解决无向图求桥的问题的代码：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 1e5 + 5;

int n, m, tot, num;
int head[MAXN], dfn[MAXN], low[MAXN], fa[MAXN], bridge[MAXN];
bool vis[MAXN];

struct Edge {
    int to, next;
} edge[MAXN << 1];

inline void add_edge(int u, int v) {
    edge[++tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot;
}

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

void tarjan(int u, int pre) {
    dfn[u] = low[u] = ++num;
    vis[u] = true;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (dfn[u] < low[v]) bridge[i] = bridge[i ^ 1] = true; // 标记桥
            else fa[v] = u; // 合并连通块
        } else if (i != (pre ^ 1)) {
            low[u] = min(low[u], dfn[v]);
            fa[u] = find(v);
        }
    }
}

void dfs(int u) {
    vis[u] = true;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (!vis[v]) {
            if (!bridge[i]) cout << u << " " << v << endl; // 输出桥
            dfs(v);
        }
    }
}

int main() {
    cin >> n >> m;
    tot = 1;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    for (int i = 1; i <= n; i++) fa[i] = i; // 初始化并查集
    tarjan(1, 0);
    memset(vis, false, sizeof(vis));
    dfs(1);
    return 0;
}

代码中使用了基准法+并查集+DFS除环方法来求无向图中的桥，具体实现过程如下：

1. 首先进行图的输入，并将边存储到邻接表中；
2. 定义一个并查集，用于维护连通块；
3. 使用Tarjan算法进行DFS遍历，对于每个节点u，进行如下处理：
- 对于u的每个邻接节点v，如果v未被访问过，则对v进行DFS遍历；
- 在回溯时，如果u的某个邻接节点v的dfn值小于u，则说明(u,v)不是桥，将(u,v)所对应的桥标记为false；
- 如果u的某个邻接节点v的dfn值大于等于u，则说明(u,v)是桥，将(u,v)所对应的桥标记为true，并在这里进行并查集合并操作；
4. 对于所有的桥，输出桥两端节点的编号。

希望能够帮助到你！

c++使用后并查集找到无向图中的桥，不使用tarjan算法的代码

下面是使用 C++ 实现使用并查集找到无向图中的桥的代码，不使用 Tarjan 算法：

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

const int MAXN = 1e5 + 5;

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

struct Edge {
    int to, nxt;
} e[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]) {
                printf("%d %d is bridge\n", u, v);
            } else {
                merge(u, v);
            }
        } else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    vis[u] = false;
}

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);
    return 0;
}

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

需要注意的是，这个算法的时间复杂度为 $O(m \alpha(n))$，其中 $m$ 为边数，$n$ 为节点数，$\alpha(n)$ 是反阿克曼函数的某个值，可以认为是一个非常小的常数。