1 条题解
-
0
AC代码:
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int n, m, dfn[maxn], low[maxn], idx; struct Edge { int v, id; }; vector<Edge> g[maxn]; bool cut[maxn*2]; void tarjan(int u, int pe) { dfn[u] = low[u] = ++idx; for (auto e : g[u]) { int v = e.v, id = e.id; if (id == pe) continue; if (!dfn[v]) { tarjan(v, id); low[u] = min(low[u], low[v]); } else low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) cut[pe] = true; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); g[u].push_back({v, i}); g[v].push_back({u, i}); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0); int cnt = 0; for (int i = 1; i <= m; i++) cnt += cut[i]; printf("%d\n", cnt); for (int i = 1; i <= m; i++) if (cut[i]) printf("%d ", i); return 0; }
- 1
信息
- ID
- 69
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 3
- 已通过
- 3
- 上传者