萌新求条QAQ
查看原帖
萌新求条QAQ
1092647
dddvag_21楼主2024/11/27 15:20
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int head[N],nxt[N],to[N],dfn[N],cnt=-1,low[N],sc=0; //链式前向星
set<int>st;
void add(int u,int v){
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void dfs(int u,int sta){ //板子?吧
    dfn[u]=low[u]=++sc;
    int son=0;
    for(int i=head[u];i!=-1;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]){
            dfs(v,sta);
            if((u==sta&&++son>1)||(u!=sta&&dfn[u]<=low[v]))st.insert(u);
        }
        low[u]=min(low[u],low[v]);
    }
}
void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)head[i]=-1,low[i]=0;
    cnt=-1,sc=0;
    st.clear();
    while(m--){
        int a,b;cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])dfs(i,i);
    cout<<st.size()<<"\n";
    for(const int x:st)cout<<x<<" ";
}
int main(){
    ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    solve();
}

24分,测试点中少了很多割点

2024/11/27 15:20
加载中...