洛谷U640024 找割边 题解

题目链接：https://www.luogu.com.cn/problem/U640024

边双连通分量 求 割边（桥） 模板题。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5, maxm = 1e5 + 5;struct Edge {int v, id;
};
vector<Edge> g[maxn];
int n, m, dfn[maxn], low[maxn], ts;
set<int> st; // 记录所有割边的编号void tarjan(int u, int eid) {dfn[u] = low[u] = ++ts;for (auto &[v, id] : g[u]) {if (id == eid) continue;if (!dfn[v]) tarjan(v, id);low[u] = min(low[u], low[v]);if (low[v] > dfn[u])st.insert(id);}
}int main() {scanf("%d%d", &n, &m);for (int i = 1, u, v; i <= m; i++) {scanf("%d%d", &u, &v);g[u].push_back({v, i});g[v].push_back({u, i});}tarjan(1, -1);if (st.size() == 0)puts("no");else {for (auto u : st)printf("%d\n", u);}return 0;
}