Tarjan求割点
概述
在一个无向图中，若删除某个点u后连通分量数目增加，则称点u为该无向图的一个割点
引理
无向连通图DFS树
从一个节点出发进行DFS，将后访问的结点设为前访问结点的孩子，DFS经过的边叫做DFS树的树边，连接结点和其非父亲祖先的边叫做返祖边
无向连通图的DFS树只存在树边和返祖边，不存在回边和横叉边（在有向弱连通图中会讲到，回边是结点指向其父亲的边，横叉边是从一个子树指向另一个子树的边）
证：1、不存在回边：无向图的边无方向，故不存在回边（无重边时）
2、不存在横叉边：假设有横叉边(u,v)，假设u比v先访问，则DFS是一定会通过u访问到v，进而访问到它的祖先及子树（貌似不是很严谨？）
定义
dfn[u]表示进入结点u的时间（相对时间戳）
low[u]表示点u及其子树中的节点通过非树边可以访问到的dfn值最小（高度最高）的结点的dfn值
算法描述
- 从起点开始DFS
- 访问一个节点，初始化其dfn值和low值均为当前时间戳（每个结点初始化可以到达dfn指最小（高度最高）的结点是自己）
- 枚举当前结点的相连结点
- 若目标结点已访问过（是当前结点的祖先），更新当前结点的low值（low[u]=min(low[u],dfn[v])）
- 若目标结点未访问过（是当前结点的孩子），则对目标结点DFS，并在回溯后用目标结点的low值更新当前结点的low值（low[u]=min(low[u],low[v])）
- 判断当前结点是否为割点
- 若当前结点为根节点，当且仅当当前结点有不少于两个子树时当前结点为割点
- 若当前结点为非根节点，当且仅当当前结点有不少于一个孩子的low值不小于当前结点的dfn值
理解
若当前结点为根节点，当且仅当当前结点有不少于两个子树时当前结点为割点
因为无向连通图的DFS树无横叉边，所以显然当根节点有不少于两个子树时当前结点为割点
若当前结点为非根节点，当且仅当当前结点有不少于一个孩子的low值不小于当前结点的dfn值
若孩子的low值小于当前结点的dfn值，说明上（当前结点的祖先）下（孩子及其子树）在树边之外有边相连，删去当前结点仍连通（不增加连通分量的数量）。因为每个子树均独立，所以当且仅当当前结点至少有一个孩子的low值≥当前结点的dfn值时，当前结点为割点
此处用图象记忆可以加强理解且不易写错
模板
洛谷3388
写代码的时候有个小tip：对于每个结点，我们只需要当前结点的low值和其子树中结点的low值，且low值是不断向上更新的，所以我们不需要将low值存放在数组中，只需要写成DFS返回值即可。
另外模板中不是无向连通图，那么只需要将所有的节点都扫描一遍，从未访问过结点的开始DFS即可
代码如下：
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int dfn[1000001];//保存时间戳 5 int dfs_clock;//当前时间 6 int ans[1000001],num;//保存答案 7 struct edge 8 { 9 int to,pre; 10 }edges[2000001]; 11 int head[1000001],tot;//邻接矩阵存图 12 int tarjan(int x,int fa)//tarjan求割点 13 { 14 int lowu=dfn[x]=++dfs_clock;//初始化low和dfn 15 short child=0,pd=0;//孩子数，是否有子树的low值不小于当前结点的dfn值 16 for(int i=head[x];i;i=edges[i].pre)//扫描所有的边 17 { 18 if(!dfn[edges[i].to])//目标结点未访问过（树边） 19 { 20 ++child; 21 int lowv=tarjan(edges[i].to,x);//目标结点的low值 22 if(lowv>=dfn[x])//目标结点low不小于当前结点dfn，当前结点是割点 23 pd=1; 24 lowu=min(lowu,lowv);//更新lowu 25 } 26 else//目标结点未访问过（返祖边） 27 lowu=min(lowu,dfn[edges[i].to]); 28 } 29 if(x==fa&&child>1)//根节点的子树不少于2个 30 ans[++num]=x; 31 else if(x!=fa&&pd)//非根节点至少有一个子树low值不小于当前结点的dfn值 32 ans[++num]=x; 33 return lowu; 34 } 35 inline void add(int x,int y)//邻接表存边 36 { 37 edges[++tot].to=y; 38 edges[tot].pre=head[x]; 39 head[x]=tot; 40 } 41 int main() 42 { 43 int n,m; 44 scanf("%d%d",&n,&m); 45 for(int i=1;i<=m;i++) 46 { 47 int x,y; 48 scanf("%d%d",&x,&y); 49 add(x,y),add(y,x); 50 } 51 for(int i=1;i<=n;i++)//遍历n个点tarjan 52 if(!dfn[i]) 53 tarjan(i,i); 54 sort(ans+1,ans+1+num); 55 printf("%d\n",num); 56 for(int i=1;i<=num;i++) 57 printf("%d ",ans[i]); 58 printf("\n"); 59 return 0; 60 }
割点模板
洛谷的数据范围有毒！明明不止10^5！大家打模板时要把数组开成成10^6！