社区讨论
爆0求助
P3388【模板】割点(割顶)参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @locpj3aw
- 此快照首次捕获于
- 2023/10/30 17:38 2 年前
- 此快照最后确认于
- 2023/11/05 04:29 2 年前
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#define rep(i,l,r)for(int i=l;i<=r;i++)
#define N 200010
#define M 100010
#define LL long long
using namespace std;
struct edge{
int to,next;
}e[2*N];
int n,m;
int u,v,w;
int head[N],cnt;
int num[N],low[N],flag[N],idx;
LL ans=0;
void add_edge(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int cur,int fa)
{
int child=0;
idx++;
num[cur]=idx;
low[cur]=idx;
for(int i=head[cur];i!=-1;i=e[i].next)
{
int tmp=e[i].to;
if(!num[tmp])
{
dfs(tmp,fa);
low[cur]=min(low[cur],low[tmp]);
if(cur!=fa&&low[tmp]>=num[cur])
flag[cur]=1;
if(cur==fa)
child++;
}
low[cur]=min(low[cur],num[tmp]);
}
if(child>=2&&cnt==fa)
flag[cnt]=1;
return ;
}
int main()
{
memset(head,-1,sizeof(head));
memset(num,0,sizeof(num));
memset(flag,0,sizeof(flag));
scanf("%d%d",&n,&m);
rep(i,1,m)
{
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
rep(i,1,n)
if(num[i]==0)dfs(i,i);
rep(i,1,n)
{
if(flag[i])ans++;
}
printf("%lld\n",ans);
rep(i,1,n)
if(flag[i])printf("%d ",i);
printf("\n");
return 0;
}

回复
共 2 条回复,欢迎继续交流。
正在加载回复...