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