社区讨论
WA 44 pts 求调
P3388【模板】割点(割顶)参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mhjt79vn
- 此快照首次捕获于
- 2025/11/04 08:06 4 个月前
- 此快照最后确认于
- 2025/11/04 08:06 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5, M = 1e5 + 5;
int n, m;
int dfn[N], low[N], tim;
bool cv[N], cnt_cv, vis[N];
int head[N], idx;
struct edge{int to, ne;} e[M << 1];
void add(int u, int v)
{
++idx;
e[idx].to = v;
e[idx].ne = head[u];
head[u] = idx;
}
void tarjan(int u, int fa)
{
vis[u] = 1;
dfn[u] = low[u] = ++tim;
int son = 0;
for (int i = head[u]; i; i = e[i].ne)
{
int v = e[i].to;
if (!vis[v])
{
++son;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (fa != u && low[v] >= dfn[u] || fa == u && son >= 2)
cv[u] = 1;
}
else if (v != fa)
low[u] = min(low[u], dfn[v]);
}
return;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i])
tarjan(i, i);
for (int i = 1; i <= n; ++i)
cnt_cv += cv[i];
printf("%d\n", cnt_cv);
for (int i = 1; i <= n; ++i)
if (cv[i])
printf("%d ", i);
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...