社区讨论

萌新,啥都不会,求助

P3388【模板】割点(割顶)参与者 7已保存回复 19

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
19 条
当前快照
1 份
快照标识符
@mi85x18h
此快照首次捕获于
2025/11/21 09:09
4 个月前
此快照最后确认于
2025/11/21 09:46
4 个月前
查看原帖
RT,WA爆0,样例测过,自造垃圾数据测过,有的多了有的少了有的求错了,求助
CPP
#include <iostream>
#include <cstdio>
#define yycoi 0
const int N=20000;
const int M=100000;
inline int mymin(int x, int y)
{
	return x<y?x:y;
}
inline int mymax(int x, int y)
{
	return x>y?x:y;
}
int n, m;
struct cfs
{
	int to, nxt;
} edge[2*M+20];
int head[N+10];
inline void add_edge(int f, int t)
{
	++head[0];
	edge[head[0]].to=t;
	edge[head[0]].nxt=head[f];
	head[f]=head[0];
	return;
}
int fa[N+10];
// book[i] == i deleted?
bool book[N+10], vis[N+10];
int dfn[N+10], low[N+10];
int ans;
void tarjan(int i)
{
	int child=0;
	vis[i]=1;
	++dfn[0];
	dfn[i]=dfn[0];
	low[i]=dfn[0];
	for (int j=head[i]; j!=-1; j=edge[j].nxt)
	{
		int t=edge[j].to;
		if (t==fa[i])
			continue;
		if (vis[t])
		{
			low[i]=mymin(low[i], dfn[t]);
		}
		else
		{
			++child;
			fa[t]=i;
			tarjan(t);
			low[i]=mymin(low[i], low[t]);
		}
		if (fa[i]!=0&&low[t]>=dfn[i])
		{
			if (!book[i])
				book[i]=true, ++ans;
		}
	}
	if (fa[i]==0&&child>=2)
	{
		if (!book[i])
			book[i]=true, ++ans;
	}
	return;
}
int main()
{
	#if yycoi==1
	freopen("tmp.in", "r", stdin);
	freopen("tmp.out", "w", stdout);
	#endif // yycoi
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; ++i)
		head[i]=-1;
	for (int i=1; i<=m; ++i)
	{
		int f, t;
		scanf("%d%d", &f, &t);
		add_edge(f, t);
		add_edge(t, f);
	}
	for (int i=1; i<=n; ++i)
		if (!vis[i])
			tarjan(i);
	#if yycoi==2
	for (int i=1; i<=n; ++i)
		printf("dfn[%d]=%d, low[%d]=%d\n", i, dfn[i], i, low[i]);
	#endif // yycoi
	printf("%d\n", ans);
	for (int i=1; i<=n; ++i)
		if (book[i])
			printf("%d\n", i);
	return 0;
}

回复

19 条回复,欢迎继续交流。

正在加载回复...