社区讨论

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 条回复,欢迎继续交流。

正在加载回复...