玄关求助!!!割点 马风良好求调
查看原帖
玄关求助!!!割点 马风良好求调
1399216
_Gloaming_楼主2024/11/11 10:28
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e4+10,M=1e5+10;
inline int rd()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9')
    {if(c=='-')f=-1;c=getchar();}
    while(c<='9'&&c>='0')
    {x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct node
{
    int u,v,ne;
}e[M];
int n,m,cnt=1,tot=0,kid;
int h[N],dfn[N],low[N];
int ans[N];
void add(int u,int v)
{
    cnt++;
    e[cnt].u=u;
    e[cnt].v=v;
    e[cnt].ne=h[u];
    h[u]=cnt;
}
void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++tot;
    kid=0;
    for(int i=h[x];i;i=e[i].ne)
    {
        int v=e[i].v;
        if(!dfn[v])
        {
            kid++;
            tarjan(v,fa);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x] && x!=fa)
                ans[x]=1;
        }
        else
            low[x]=min(low[v],low[x]);
    }
    if(x==fa && kid>=2)
        ans[x]=1;
}
int main()
{
    n=rd();m=rd();
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=m;i++)
    {
        int x,y;
        x=rd();y=rd();
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            tarjan(i,i);
    }
    int k=0;
    for(int i=1;i<=n;i++)
    {
        if(ans[i])
            k++;
    }
    printf("%d\n",k);
    for(int i=1;i<=n;i++)
    {
        if(ans[i])
            printf("%d ",i);
    }
}

样例过了 2359RE 其他全WA

2024/11/11 10:28
加载中...