#11 WA 92pts求调 玄关
查看原帖
#11 WA 92pts求调 玄关
798144
SukiYuri楼主2023/12/18 21:48

调不动了

#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e4,maxm=2*1e5;
int low[maxn],dfn[maxn],head[maxn],r,ans=0,cnt=0,n,m;
bool is[maxn];
struct node{
    int fm,to,nxt;
}E[maxm];
inline void adde(int u,int v){
    ++cnt;
    E[cnt].fm=u;
    E[cnt].to=v;
    E[cnt].nxt=head[u];
    head[u]=cnt;
}
void tarjan(int cu){
    int ch=0;
    dfn[cu]=low[cu]=++cnt;
    for(int i=head[cu];i;i=E[i].nxt){
        int to=E[i].to;
        if(!dfn[to]){
            ch++;
            tarjan(to);
            low[cu]=min(low[cu],low[to]);
            if(dfn[cu]<=low[to]&&cu!=r){
                ans+=!is[cu];
                is[cu]=1;
            }
        }
        else low[cu]=min(low[cu],dfn[to]);
    }
    if(cu==r&&ch>=2){
        ans+=!is[cu];
        is[cu]=1;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        adde(u,v);
        adde(v,u);
    }
    cnt=0;
    for(int i=1;i<=n;++i)
        if(!dfn[i])r=i,tarjan(i);
    cout<<ans<<endl;
    for(int i=1;i<=n;++i)
        if(is[i])cout<<i<<" ";
    return 0;
}
2023/12/18 21:48
加载中...