Tarjan无向图的割点和桥（割边）

前置知识：

回忆并查集维护连通块：

1. 对于每一个连通块 维护一颗有根树，$pre[x]$pre[x]表示$x$x的父亲。
2. 则假设我们要添加一条边$(u,v)$(u,v)，首先求出$u,v$u,v所在的连通块的有根树树根$fu,fv$fu,fv，然后令$pre[fu]=fv$pre[fu]=fv。
3. $Find(x):$Find(x):若$pre[x]=x$pre[x]=x则return x，否则return pre[x]=Find(pre[x])。

割点：

删掉这个点和这个点有关的边，图就不是连通图，分裂成为了多个不相连的子图。

割边（桥）：

4. 对于一个连通的无向图，定义一条边$(u,v)$(u,v)是桥，当且仅当断开这条边后的图变得不连通。
5. 图的大致形状：$O-O$O−O，则中间的边就是桥。
6. 强连通分量：没有桥的连通块。

Tarjan：

7. 时间戳：对整图进行$dfs$dfs，设$dfn[x]$dfn[x]表示点$x$x是第几个被搜到的($DFS序$DFS序)。

DFS序：

这里不得不提一下的是$DFS序$DFS序，顾名思义，$DFS序$DFS序就是对一个图进行$DFS$DFS时候的顺序：

8. $subtree(x)$subtree(x)表示搜索树中以节点$x$x为根的子树节点集合。

如上图：$subtree(2)=(2,3,4,5)$subtree(2)=(2,3,4,5)

9. 追溯数组：$low[x]$low[x]表示：追溯，追溯，就是寻找以$x$x节点为根,可以抵达的最小的$dfn$dfn。

也就是这些节点的时间戳的最小值。
这些包括;
1.$subtree(x)$subtree(x)中的节点
2.通过一条不在搜索树上的边，能够抵达$subtree(x)$subtree(x)中的节点。

判定法则：

参见这篇博客：https://blog.csdn.net/nuoyanli/article/details/103421151

模板：

割边模板：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+20;
int head[N],edge[N<<1],Next[N<<1],tot;
int dfn[N],low[N],n,m,num;
bool bridge[N<<1];
void add_edge(int a,int b) {
	edge[++tot]=b;
	Next[tot]=head[a];
	head[a]=tot;
}
void Tarjan(int x,int Edge) {
	dfn[x]=low[x]=++num;//DFS序标记
	for(int i=head[x]; i; i=Next[i]) { //访问所有出边
		int y=edge[i];//出边
		if (!dfn[y]) { //不曾访问过,也就是没有标记,可以认为是儿子节点了
			Tarjan(y,i);//访问儿子节点y,并且设置边为当前边
			low[x]=min(low[x],low[y]);//看看能不能更新,也就是定义中的,subtree(x)中的节点 最小值为low[x]
			if (low[y]>dfn[x]) { //这就是桥的判定
				bridge[i]=bridge[i^1]=true;//重边也是桥
			}
		} else if (i!=(Edge^1)) {
			low[x]=min(low[x],dfn[y]);
		}//第二类定义,也就是通过1跳不在搜索树上的边,能够抵达 subtree(x)的节点
	}
}
int main() {
	scanf("%d%d",&n,&m);
	tot=1;//边集从编号1开始
	for(int i=1; i<=m; i++) {
		int a,b;
		scanf("%d%d",&a,&b);
		add_edge(a,b);
		add_edge(b,a);
	}
	for(int i=1; i<=n; i++) {
		if (!dfn[i]) { //一个无向图,可能由多个搜索树构成
			Tarjan(i,0);
		}
	}

	for(int i=2; i<=tot; i+=2) { //无向边不要管,直接跳2格
		if (bridge[i]) {
			printf("%d %d\n",edge[i^1],edge[i]);//桥的左右两端
		}
	}
	return 0;
}

割点模板：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+20;
int head[N],edge[N<<1],Next[N<<1],tot;
int dfn[N],low[N],n,m,num,root,ans;
bool cut[N];
void add_edge(int a,int b) {
	edge[++tot]=b;
	Next[tot]=head[a];
	head[a]=tot;
}
void Tarjan(int x) {
	dfn[x]=low[x]=++num;//DFS序标记
	int flag=0;
	for(int i=head[x]; i; i=Next[i]) { //访问所有出边
		int y=edge[i];//出边
		if (!dfn[y]) { //不曾访问过,也就是没有标记,可以认为是儿子节点了
			Tarjan(y);//访问儿子节点y,并且设置边为当前边
			low[x]=min(low[x],low[y]);//看看能不能更新,也就是定义中的,subtree(x)中的节点 最小值为low[x]
			if (low[y]>=dfn[x]) { //这就是割点的判定
				flag++;//割点数量++
				if (x!=root || flag>1) { //不能是根节点,或者说是根节点,但是有至少两个子树节点 是割点
					cut[x]=true;
				}
			}
		} else low[x]=min(low[x],dfn[y]); //第二类定义,也就是通过1跳不在搜索树上的边,能够抵达 subtree(x)的节点
	}
}
int main() {
	scanf("%d%d",&n,&m);
	memset(cut,false,sizeof(cut));
	for(int i=1; i<=m; i++) {
		int a,b;
		scanf("%d%d",&a,&b);
		add_edge(a,b);
		add_edge(b,a);
	}
	for(int i=1; i<=n; i++) {
		if (!dfn[i]) { //一个无向图,可能由多个搜索树构成
			root=i,Tarjan(i);
			for(int i=1; i<=n; i++) { //统计割点个数
				if (cut[i]) {
					ans++;
				}
				printf("%d\n",ans);
				for(int i=1; i<=n; i++) { //顺序遍历,康康哪些点是割点
					if (cut[i]) {
						printf("%d ",i);
					}
				}
			}
		}
	}
	return 0;
}