Tarjan求割点 || Luogu P3388 【模板】割点（割顶）

题解：无
代码：
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define max(a,b) ((a)>(b)?(a):(b))
 5 #define min(a,b) ((a)<(b)?(a):(b))
 6 using namespace std;
 7 const int maxn=20000,maxm=1e5;
 8 int N,M,num_edge=0,edge_head[maxn+50],u,v,DFN[maxn+50],LOW[maxn+50];
 9 int ix=0,son,g[maxn+50],ans=0;
10 struct Edge{
11     int to,nx;
12 }edge[maxm*2+50];
13 inline void Add_edge(int from,int to){
14     edge[++num_edge].nx=edge_head[from];
15     edge[num_edge].to=to;
16     edge_head[from]=num_edge;
17     return;
18 }
19 void Tarjan(int x,int fa){
20     DFN[x]=LOW[x]=++ix;
21     for(int i=edge_head[x];i;i=edge[i].nx){
22         int y=edge[i].to;
23         if(fa!=y){
24             if(DFN[y]==0){
25                 if(fa==0)son++;
26                 Tarjan(y,x);
27                 LOW[x]=min(LOW[x],LOW[y]);
28                 if(fa!=0&&DFN[x]<=LOW[y]&&g[x]==0){
29                     g[x]=1;
30                     ans++;
31                 }
32             }
33             else LOW[x]=min(LOW[x],DFN[y]);            
34         }
35     }
36     return;
37 }
38 int main(){
39     scanf("%d%d",&N,&M);
40     for(int i=1;i<=M;i++){
41         scanf("%d%d",&u,&v);
42         Add_edge(u,v);
43         Add_edge(v,u);
44     }
45     for(int i=1;i<=N;i++)
46         if(DFN[i]==0){
47             son=0;
48             Tarjan(i,0);
49             if(son>1&&g[i]==0){
50                 g[i]=1;
51                 ans++;
52             }
53         }
54     printf("%d
",ans);
55     for(int i=1;i<=N;i++)if(g[i])printf("%d ",i);
56     return 0;
57 }
By:AlenaNuna