P3388 【模板】割点（割顶） 题解

一、题目描述：

　　给你一个 $n$ 个点，$m$ 条边的无向图。

　　求出所有割点，按节点编号升序排序。

　　数据范围：$1 \le n \le 2\times 10^4,1 \le m \le 1 \times 10^5$ 。

 二、解题思路：

　　板子题，不需要思路。时间复杂度 $O(n+m)$ 。

 三、完整代码：

 1 #include<iostream>
 2 #define N 20010
 3 #define M 100010
 4 using namespace std;
 5 int n,m,rt,cc,tot,num;
 6 int ans[N],dfn[N],low[N];
 7 struct EDGE{
 8     int v,nxt;
 9 }edge[M*2];
10 int head[N],cnt;
11 void add(int u,int v)
12 {
13     edge[++cnt].v=v;
14     edge[cnt].nxt=head[u];
15     head[u]=cnt;
16 }
17 void tarjan(int u)
18 {
19     dfn[u]=low[u]=++tot;int son=0;
20     for(int i=head[u];i!=-1;i=edge[i].nxt)
21     {
22         int to=edge[i].v;
23         if(!dfn[to]){
24             //就是说，这是一颗以u为根的子树了
25             //且它至少与当前访问过的其他子树独立 
26             son++;tarjan(to);
27             low[u]=min(low[u],low[to]); 
28             //反正是我的子树了
29             //low[u]代表这颗子树能到达的最小dfn吧 
30             if(low[to]>=dfn[u]&&u!=rt)
31                 num+=ans[u]==0,ans[u]=1;
32             //如果说当前子树被隔断，自然u就是割点 
33         }else    low[u]=min(low[u],dfn[to]);
34     }
35     if(son>=2&&u==rt) num+=ans[u]==0,ans[u]=1;
36     //特殊判断根节点，很容易理解 
37 }
38 int main()
39 {
40     ios::sync_with_stdio(false);
41     cin.tie(0);cout.tie(0);
42     cin>>n>>m;
43     for(int i=1;i<=n;i++)
44         head[i]=-1;
45     for(int i=1,u,v;i<=m;i++)
46         cin>>u>>v,add(u,v),add(v,u);
47     for(int i=1;i<=n;i++)
48         if(!dfn[i]) rt=i,tarjan(i);
49     //tarjan，一个还不错的算法 
50     cout<<num<<'\n';
51     for(int i=1;i<=n;i++)
52         if(ans[i])    cout<<i<<" ";
53     return 0;
54 }

四、写题心得：

　　今天本来学的是圆方树，结果我连点双是什么我都不知道，先来学了割点。收获经验如下：

　　$1、割点需要特殊判断根节点=> Exp++$

　　$2、根本不用排序，记录答案即可（好吧这好像是桶排）=> Exp++$