听灌多求调
  • 板块灌水区
  • 楼主again_q
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/10/17 21:44
  • 上次更新2024/10/18 09:28:00
查看原帖
听灌多求调
723168
again_q楼主2024/10/17 21:44

P3388

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e4+10;
struct edge{
    int ed,next;
}b[N];
int nbs[N],tot=0,dfn[N],low[N],t,root,cnt=0;
bool gd[N];
void add(int x,int y){
    tot++;
    b[tot].next=nbs[x];
    b[tot].ed=y;
    nbs[x]=tot;
}
void tarjan(int k){
    low[k]=dfn[k]=++t;
    int son=0;
    for(int x=nbs[k];x;x=b[x].next){
        int u=b[x].ed;
        if(!dfn[u]){
            son++;
            tarjan(u);
            low[k]=min(low[k],low[u]);
            if(low[u]>=dfn[k] && k!=root && !gd[u]){
                cnt++;
                gd[u]=1;
            }
        }else{
            low[k]=min(low[k],dfn[u]);
        }
    }
    if(son>=2 && k==root && !gd[k]){
        cnt++;
        gd[k]=1;
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);add(y,x);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            root=i;
            tarjan(i);
        }
    }
    cout<<cnt<<endl;
    for(int i=1;i<=n;i++){
        if(gd[i]){
            cout<<i<<" ";
        }
    }
    return 0;
}


2024/10/17 21:44
加载中...