12分球注
查看原帖
12分球注
555065
ChrysanthBlossom楼主2022/10/12 13:55

只A了最后一个点(貌似割点多于一个就WA了?可是自己写了几个多于一个割点的情况,最后也没事啊)

#include<bits/stdc++.h>
#define maxn 20005
#define ri register int
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
int n,m,cnt;
vector<int>e[maxn];
int dfn[maxn],low[maxn];
bool cut[maxn];
void tarjan(int u,int fa){
    dfn[u]=low[u]=++cnt;
    int v,col=0;
    for(ri i=0;i<e[u].size();i++){
        v=e[u][i];
        if(!dfn[v]){
            col++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(col>1&&u==1||u^1&&low[v]>=dfn[u])cut[u]=1;
        }else if(v^fa)low[u]=min(low[u],dfn[v]);
    }
}
signed main(){
    n=read();m=read();
    for(ri i=1;i<=m;i++){
        int u,v;
        u=read();v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }cnt=0;
    for(ri i=1;i<=n;i++)if(~dfn[i])tarjan(i,i);
    int tot=0;
    for(ri i=1;i<=n;i++)if(cut[i])tot++;
    printf("%d\n",tot);
    for(ri i=1;i<=n;i++)if(cut[i])printf("%d ",i);
    return 0;
}
2022/10/12 13:55
加载中...