P3388 80pts WAon#11 #12
查看原帖
P3388 80pts WAon#11 #12
617065
Ovine楼主2024/11/29 16:05

求调,实在太菜不知道错哪了

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e4+8;
const int MAXM=1e5+8;
int n,m,cnt;
int fa[MAXN],fis[MAXN],dfn[MAXN],low[MAXN];
bool cut[MAXN];
int tim;
struct
{
    int u,v,nxt;
}e[MAXM*2];
void add(int x,int y)
{
    cnt++;
    e[cnt].u=x;
    e[cnt].v=y;
    e[cnt].nxt=fis[x];
    fis[x]=cnt;
}

void dfs(int x)
{
    tim++;
    dfn[x]=tim;
    low[x]=tim;
    int child=0;
    for(int i=fis[x];i;i=e[i].nxt)
    {
        int y=e[i].v;
        if(dfn[y]==0)
        {
            child++;fa[y]=x;
            dfs(y);
            if(fa[x]==-1&&child>=2)cut[x]=1;
            if(fa[x]!=-1&&low[y]>=dfn[x])cut[x]=1;
            low[x]=min(low[x],low[y]);
        }
        else if(fa[x]!=y)
        {
            low[x]=min(low[x],low[y]);
        }
    }
}

int main()
{
    memset(fa,-1,sizeof(fa));
    cin>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)dfs(i);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(cut[i])ans++;
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)
    {
        if(cut[i])cout<<i<<' ';
    }
    return 0;
}
    
2024/11/29 16:05
加载中...