各种Tarjan算法详解

$\text{Tarjan}$算法是图论中实用/常用的算法之一，能解决强连通分量，双连通分量，割点和桥，求$\text{LCA}$等问题，本文将对以上用途一一介绍

• 注意：本文对强连通分量的介绍已经完成，而其他部分尚未完成。

前言

$\text{Tarjan}$算法是图论中实用/常用的算法之一，能解决强连通分量，双连通分量，割点和桥，求$\text{LCA}$等问题，本文将对以上用途一一介绍

强连通分量

定义

一个强连通分量是指一个有向图中的最大强联通子图。

• 强联通子图：任意两点可以互相到达的有向图。

如下图，就有3个强联通分量：{1,2,3}，{4}，{5}。

做法

（一）如何找强联通分量。

进行$\text{Dfs}$遍历，在$\text{Dfs}$树上操作。如果在$\text{Dfs}$时发现遍历到了一个访问过的的点（如下图的$1$号节点），那么说明从这个点出发，可以回到自己，即这条路径构成了一个环，环上的点是强联通的。

但根据强联通分量的定义，这只能说明他们在同一个强联通分量内，不能保证他们就是一个强连通分量，还要接着处理。

（二）找完整的强联通分量。

考虑什么情况下才能保证上述的环构成一个强连通分量。上述的环都是由一个节点$S$和它在Dfs树中的子树构成的，那么只要保证子树内没有节点连向$S$的祖先，即可保证这是一个强连通分量。

原因比较好理解：若该点子树中有点连向了他的祖先，那么他的祖先便属于这个强连通分量，显然可以构成一个更大的强联通图。

可以参见下图辅助理解。图中$2$号节点的子树中，$4$号节点连向了$2$的父亲——$1$号点，那么环{2,3,4}就属于强联通分量{1,2,3,4}，而不能单独构成强联通分量。

（三）找准确的强连通分量。

以上的算法貌似还有一个问题：我们能通过第二条（二）找完整的强联通分量。找到强联通分量所在的子树，但是我们并不知道子树中哪些节点属于，哪些节点不属于。

解决办法：

就像$\text{Dfs}$找环一样，用一个栈记录即可。

$u$之后的所有点在u被回溯到时$u$和栈中所有在它之后的点都构成强连通分量。
具体见代码实现。

然后各位神仙们就可以脑补代码实现了，本次就到这里，感谢阅读！

程序实现

定义一些数组：

int dfn[N];//表示在Dfs时是第几个被搜到的
int low[N];//表示这个点的子树节点及他们连向的点的最小$dfn$值。为了实现上面的第二步
int sta[N};//
int vis[N];//记录点是否在栈中

实现过程

1.最外层框架是对树的$\text{Dfs}$。

2.每遍历到一个节点$u$:

(1)初始化dfn[u]=low[u]=++cnt(cnt是计数器）。

根据数组含义可以理解，在处理前，子树中dfn最小的就是dfn[u],所以把low[u]初始化为dfn[u]

(2)把$u$入栈，标记vis[u]=1

(3)接着遍历它所能到达的节点$v$，判断$v$是否访问过（方法：看dfn值是否等于0）。

a.未访问过：接着递归Dfs(v)，并用$v$的$low$值更新$u$:
low[u]=min(low[u],low[v])
因为子树中的节点可能连向$u$的祖先节点，所以按照$dfn$的含义更新它。

b.访问过：

如果$v$在栈中，说明$u$,$v$在一个强连通分量，那么更新low[u]:low[u]=min(low[u],low[v])

如果不在栈中，说明$u$不能到达$v$,二者没有关联，不进行处理。

(4) 处理完$u$的子树后：

此时dfn[u]和low[u]都已经确定好。若dfn[u]==low[u]，根据数组含义，表明$u$是子树中所有点能到达的dfn最小的点，这也就满足了上文中的（二）找完整的强联通分量。（还记得吗），即满足了：u点与它的子孙节点构成了一个最大的强连通图,即强连通分量。

这时我们只需把栈中$u$后面的点和$u$一并弹出（别忘更新$\text{vis}$），弹出的这些点就是一个强连通分量了。

代码

Tarjan

建议参照上文对比阅读代码。

int dfn[N],low[N],t;//数组定义同上面的解释
int sta[N],top;
int vis[N];
int col[N],tot;//用于标记答案，col相同的点在一个强连通分量中
void Tarjan(int u)
{
	low[u]=dfn[u]=++t;
	sta[++top]=u;
	vis[u]=1;
	for(int i=head[u];i;i=next[i])
	{
		int v=to[i];
		if(!dfn[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		int v;
		tot++;
		do{
			v=sta[top];
			top--;
			vis[v]=0;
			col[v]=tot;
		}while(u!=v);
	}
}

主函数

注意：由于图可能不连通，从一个点开始Dfs可能不会遍历所有点，所以要这样写：

for(int i=1;i<=n;i++)//遍历所有点
		if(!dfn[i]) Tarjan(i);

时间复杂度

每个点只被入栈，出栈一次，时间复杂度为$O(n)$

双连通分量、割点和桥

概念

双联通分量与强联通分量类似，是一个无向图中的最大双连通子图。它分为两类：点双连通分量，边双连通分量（简称点双，边双）。

点双连通分量、割点

定义

点双连通分量：是指一个无向图中的最大点双连通子图。

• 点双连通图：一个去掉任意一节点都不会改变它的连通性的无向图。

例如，下面这个图中，{1,2,3,4,5}就是一个点双连通分量

• 割点：若一个图中，有一点$A$,删掉该点会使图不连通，那么称点$A$为割点。

性质

根据定义可以看出，任意两点间都有至少两条点不重复的路径。

点双连通分量之间以割点连接，且两个点双连通分量之间有且只有一个割点。

割点求法

首先类似于强连通分量，Tarjan求割点也是在Dfs基础上运行的，所以先获得一个Dfs树。

• 对于根节点：比较好判断。统计一下根节点的子树个数，若 子树个数$\geq 2$，那么割掉根节点，两个子树便不再联通，即可说明根节点是割点。
• 对于非根节点：根据割点的定义和Dfs树，可以知道，割点被割掉后，图一定是被分成了割点的子树A和除子树节点外所有的点B两部分。简单点说，割掉割点相当于把子树剪掉了。经过分析，只要割掉一个点后，A和B不连通，即可保证该点是割点。也就是说，当A中的所有点，都只是通过这个点连接着B，而没有其它边连接A和B，即可说明

参考资料

https://www.cnblogs.com/stxy-ferryman/p/7779347.html

https://www.cnblogs.com/ljk123-de-bo-ke/p/10888905.html

https://www.luogu.org/blog/shiboao/post-ti-gao-ge-dian