【模板】割点（割顶）-布布扣-bubuko.com

[Time Gate] https://www.luogu.org/problemnew/show/P3388

【解题思路】

对于根节点，判断是不是割点很简单——计算其子树数量，如果有2棵即以上的子树，就是割点。因为如果去掉这个点，这两棵子树就不能互相到达。
对于非根节点，判断是不是割点就有些麻烦了。我们维护两个数组dfn[]和low[]，dfn[u]表示顶点u第几个被（首次）访问，low[u]表示顶点u及其子树中的点，通过非父子边（回边），能够回溯到的最早的点（dfn最小）的dfn值（但不能通过连接u与其父节点的边）。对于边(u, v)，如果low[v]>=dfn[u]，此时u就是割点。
假设当前顶点为u，则默认low[u]=dfn[u]，即最早只能回溯到自身。
有一条边(u, v)，如果v未访问过，继续DFS，DFS完之后，low[u]=min(low[u], low[v])；
如果v访问过（且u不是v的父亲），就不需要继续DFS了，一定有dfn[v]<dfn[u]，low[u]=min(low[u], dfn[v])。

【code】
`

 1 ``cpp
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 struct edge{
 5     int nxt,mark;
 6 }pre[200010];
 7 int n,m,idx,cnt,tot;
 8 int head[100010],DFN[100010],LOW[100010];
 9 bool cut[100010];
10 void add (int x,int y)
11 {
12     pre[++cnt].nxt=y;
13     pre[cnt].mark=head[x];
14     head[x]=cnt;
15 }
16 void tarjan (int u,int fa)
17 {
18     DFN[u]=LOW[u]=++idx;
19     int child=0;
20     for (int i=head[u];i!=0;i=pre[i].mark)
21     {
22         int nx=pre[i].nxt;
23         if (!DFN[nx])
24         {
25             tarjan (nx,fa);
26             LOW[u]=min (LOW[u],LOW[nx]);
27             if (LOW[nx]>=DFN[u]&&u!=fa)
28                 cut[u]=1;
29             if(u==fa)
30                 child++;
31         }
32         LOW[u]=min (LOW[u],DFN[nx]);
33     }
34     if (child>=2&&u==fa)
35         cut[u]=1;
36 }
37 int main()
38 {
39     memset (DFN,0,sizeof (DFN));
40     memset (head,0,sizeof (head));
41     scanf ("%d%d",&n,&m);
42     for (int i=1;i<=m;i++)
43     {
44         int a,b;
45         scanf ("%d%d",&a,&b);
46         add (a,b);
47         add (b,a);
48     }
49     for (int i=1;i<=n;i++)
50         if (DFN[i]==0)
51             tarjan (i,i);
52     for (int i=1;i<=n;i++)
53         if (cut[i])
54             tot++;
55     printf ("%d\n",tot);
56     for (int i=1;i<=n;i++)
57         if (cut[i])
58             printf ("%d ",i);
59     return 0;