C++实现用朴素算法+邻接表解决图论-桥问题

桥问题是图论中一个经典的问题，也称为割边问题。给定一个无向连通图，求其中所有的桥，即删除这条边后，图不再连通的边。下面是朴素算法+邻接表实现桥问题的C++代码：

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

const int MAXN = 10010;
int dfn[MAXN], low[MAXN], cnt;
bool bridge[MAXN];
vector<int> G[MAXN];

void dfs(int u, int fa) {   // u是当前节点，fa是u的父亲节点
    dfn[u] = low[u] = ++cnt;  // 第一次访问u，dfn[u]和low[u]都赋为cnt
    for (int i = 0; i < G[u].size(); ++i) {  // 枚举u的所有邻接点
        int v = G[u][i];
        if (!dfn[v]) {  // 如果v还没有被访问过
            dfs(v, u);
            low[u] = min(low[u], low[v]);  // 更新u的low值
            if (low[v] > dfn[u]) bridge[v] = true;  // 如果(u, v)是桥，标记v
        }
        else if (v != fa)  // 如果v已经被访问过，且不是u的父亲节点
            low[u] = min(low[u], dfn[v]);  // 更新u的low值
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) dfs(i, 0);
    for (int i = 1; i <= n; ++i)
        if (bridge[i]) cout << i << " ";
    cout << endl;
    return 0;
}

其中，`dfn[u]`表示节点u被遍历到的时间戳，`low[u]`表示节点u能够回溯到的最早的时间戳（即u能够到达的最高祖先的时间戳），`bridge[i]`表示节点i是否为桥。在dfs过程中，如果当前节点v还没有被访问过，则继续往下遍历，将v作为新的节点u，更新u的low值。如果v已经被访问过，且不是u的父亲节点，则说明(u, v)是反向边，更新u的low值即可。如果low[v] > dfn[u]，则说明(u, v)是正向边，且(v, u)不是反向边，即(u, v)是桥，标记v即可。最后输出所有的桥即可。