社区讨论
求助!!急!!
P3388【模板】割点(割顶)参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mi6z81wo
- 此快照首次捕获于
- 2025/11/20 13:14 4 个月前
- 此快照最后确认于
- 2025/11/20 13:14 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int u,v,next;
}e[200005];
int n,m,tot,x,y,head[20005],ans=0,num[20005],low[20005],ind;
bool vis[20005];
inline void add(int u,int v)
{
e[++tot].u=u;
e[tot].v=v;
e[tot].next=head[u];
head[u]=tot;
}
void tarjan(int cur,int fa)
{
int child=0;
ind++;
num[cur]=ind;
low[cur]=ind;
for(int i=head[cur];i!=-1;i=e[i].next)
{
if(num[e[i].v]==0)
{
child++;
tarjan(e[i].v,cur);
low[cur]=min(low[cur],low[e[i].v]);
if((cur!=1&&low[e[i].v]>=num[cur])||(cur==1&&child==2))
vis[cur]=true;
}
else
if(e[i].v!=fa)
low[cur]=min(low[cur],num[e[i].v]);
}
}
int main()
{
memset(head,-1,sizeof(head));
memset(vis,false,sizeof(vis));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
tarjan(1,1);
for(int i=1;i<=n;++i)
if(vis[i]) ans++;
printf("%d\n",ans);
for(int i=1;i<=n;++i)
if(vis[i]) printf("%d ",i);
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...