社区讨论

模板打炸求$diss$ $QAQ$

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

讨论操作

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

当前回复
9 条
当前快照
1 份
快照标识符
@mi7dzw65
此快照首次捕获于
2025/11/20 20:07
4 个月前
此快照最后确认于
2025/11/20 20:07
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define N 100010
using namespace std;

struct node{int x,y,next;}a[N*2];
int n,m,len=0,ans=0,tot=0;
int last[N],dfn[N],low[N],fa[N];
bool f[N];

void ins(int x,int y)
{
    a[++len].x=x;a[len].y=y;
    a[len].next=last[x];last[x]=len;
}

void tarjan(int x)
{
    int rd=0;
    dfn[x]=low[x]=tot++;
    for(int i=last[x];i;i=a[i].next)
    {
        int y=a[i].y;
        if(!dfn[y])
        {
            rd++;fa[y]=x;
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x] && x!=fa[x]) f[x]=true;
        }
        else low[x]=min(low[x],dfn[y]);
    }
    if(x==fa[x] && rd>=2) f[fa[x]]=true;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;scanf("%d %d",&x,&y);
        ins(x,y);ins(y,x);
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        if(f[i]) ans++;
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
        if(f[i]) printf("%d ",i);
    return 0;
}

回复

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

正在加载回复...