求调92pts,WA on #11
查看原帖
求调92pts,WA on #11
982938
SnowFlavour楼主2024/8/6 15:03
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>e[N];
int low[N],dfn[N];
int tot,s;
bool iscut[N];
void tarjan(int x){
    low[x]=dfn[x]=++tot;
    int cl=0;
    for(int i=0;i<e[x].size();i++){
        int v=e[x][i];
        if(!dfn[v]){
            cl++;
            tarjan(v);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x]&&x!=s){
                iscut[x]=1;
            }
        }
        else low[x]=min(low[x],dfn[v]);
    }
    if(x==1&&cl>=2)iscut[s]=1;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])s=i,tarjan(i);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(iscut[i])ans++;
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        if(iscut[i])cout<<i<<" ";
    }
    
}
2024/8/6 15:03
加载中...