社区讨论

为什么

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

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@mi7yx4ag
此快照首次捕获于
2025/11/21 05:53
4 个月前
此快照最后确认于
2025/11/21 05:53
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define M 100005
#define r(x) x=read() 
using namespace std;
inline int read()
{
	int w=0,q=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')q=-1;c=getchar();}
	while(c>='0'&&c<='9'){w=(w<<3)+(w<<1)+c-'0';c=getchar();}
	return w*q;
}
int h[(M<<1)],cnt=1,n,m,ans;
struct node{int nxt,to;}ed[(M<<1)];
void add(int fr,int to){ed[++cnt].nxt=h[fr];ed[cnt].to=to;h[fr]=cnt;}
int dfn[M],low[M],cut[M],num,root;
void tarjan(int x)
{
	dfn[x]=low[x]=++num;
	int flag=0;
	for(int i=h[x];i;i=ed[i].nxt)
	{
		int y=ed[i].to;
		if(!dfn[y])
		{
			tarjan(y,fa);
			low[x]=min(low[y],low[x]);
			if(low[y]>=dfn[x])
			{
				flag++;
				if(x!=root||flag>1)cut[x]=1;
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
int main()
{
	r(n),r(m);
	for(int i=1;i<=m;i++){int fr,to;r(fr),r(to);add(fr,to);add(to,fr);}
	for(int i=1;i<=n;i++)if(!dfn[i])root=i,tarjan(i);
	for(int i=1;i<=n;i++)if(cut[i])ans++;printf("%d\n",ans);
	for(int i=1;i<=n;i++)if(cut[i])printf("%d ",i);
	return 0;
}
CPP
为什么我没有加tarjan(int x,int fa)A了?
真的要像题解那样特判吗?
树的根节点的特判是不是只要int flag=0if(x!=root||flag>1)就行了?

回复

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

正在加载回复...