图论进阶III(Tarjan主场)

1.DFS树

作为一个重要的前置芝士，$DFS$树并不是很难，但有很多的性质需要大家发现并记忆

我们可以将任意一张图划分为只含四种边的$DFS$树，首先看下面的这张图

假设以红色节点为根进行$DFS$，我们会得到这样的一个图，其中

<1>.红色边称作"树边"，是我们进行$DFS$时所经过的所有边

<2>.黄色边称作"返祖边"，是从儿子节点返连向祖先节点的边

<3>.绿色边称作"横叉边"，是连接不存在祖先与孩子关系两点的边

<4>.蓝色边称作"前向边"，是由祖先节点连向儿子节点的非$DFS$经过边

对于任意一个图，我们都可以将它划分为至多$4$种边的树形结构

以上的边还有一些拓展性质：

<1>.横叉边(在图中)一定是由右边指向左边的一条有向边，因为如果是右边指向左边则它会在$DFS$遍历中被优先选择从而成为树边

<2>.前向边可有可无，删去前向边并不会影响图的任何连通性，因为总有一条更长节点数更多的边可以代替它，否则这条前向边就会成为树边

<3>.在进行$DFS$的同时我们会引入一个值$dfn_i$指节点$i$是第几个被搜索到的点，我们称之为"时间戳"

这就是$DFS$树的基础芝士，我们后面的内容都会围绕$DFS$树展开，热芝士：下面所涉及的所有算法均是由计算机学家$Robert E.\;\; Tarjan$老爷爷发明的且统称为$Tarjan$算法

---

2.强连通分量与缩点

强连通分量的定义是：在有向图中，如果节点$a$能够到达节点$b$且节点$b$也能到达节点$a$，那么我们说这两个节点强连通

因为这是一个$DG$(有向图)，所以容易发现如果存在一条环则环上所有点强连通

我们把这个情况放在$DFS$树上看看，首先树边保证树形结构就排除了环的出现，那什么时候会出现环呢

只有通过走横叉边或返祖边才能回到自己的祖先从而形成环对吧，这时候这个环上的所有点都强连通

这时候如何判断呢，其实就是$low\geq dfn$时，它连向了我的父亲的祖先，说明我们找到了一个环

既然要找极大的强连通分量，那么我们也要找最长的环

很简单，我们判断它是一个环的条件是$low\geq dfn$，那么当$low==dfn$的时候它就是最长的环了(不懂的可以看图理解一下)

但是要注意，我们不能通过一条横叉边到一个已经被划分好的节点上，原因也很简单，因为它已经被划分好了，所以我们不能在走过去把他放到新的强连通分量组成的环里面

在我们划分完强连通分量后，我们会发现原图变成了由多个环构成的环间节点连通的一张图

这个时候我们可以进行操作："缩点"，顾名思义，就是把一个强连通分量缩成一个新的点，强连通分量内连的边就可以省略

这样处理后，因为每个强连通分量之间都不会强连通(否则就可以合并为一个强连通分量)，我们就会得到一个$DAG$，就能使用一些特殊的方法来解决题目了(例如$topsort$)

void dfs( int p )//求强连通分量的代码，DFS遍历树边
{
	dfn[p]=low[p]=++idx;//打上时间戳(一个点能到达的最小时间戳最大就是本身)
	in[p]=true;//标记此点还没有被划分在任一的强连通分量里
	sta.push( p );//先将这个点压入栈中
	for( auto x:rode[p] )//枚举所有边
	{
		if( !dfn[x] )//这是一条树边，走过去
		{
			dfs( x );//继续递归
			low[p]=min( low[p],low[x] );//更新low
		}	
		else if( in[x] ) low[p]=min( low[p],dfn[x] );//这是一条横叉边/返祖边且并未被划分在任一强连通分量中，更新low
	}
	if( dfn[p] == low[p] )//点 p 这颗子树上是时间戳最小的一个割点
	{
		++num;//增加一个分量
		while( sta.top() != p )//将它的子树全部划分至同一个强连通分量中
		{
			sum[num]+=val[t];//计算缩点后的新点的权值
			group[sta.top()]=num;//记录每个点在那个强连通分量里
			in[sta.top()]=false;//记录这个点已经不再栈里了(被划分进了一个强连通分量)
			sta.pop();
		}
		sum[num]+=val[t];
		group[sta.top()]=num;
		in[sta.top()]=false;
		sta.pop();//也要将它自己划分进来
	}
}

for( int u=1;u<=n;u++ )
		for( auto v:rode[u] )//遍历所有的边
			if( group[u] != group[v] )//强连通分量内的点可以任意互通，不用连边
				sp_rode[group[u]].push_back( group[v] );//将缩点后的点相连

---

3.割点与桥

如果删去一个点及其对应边会使图的连通分量增加，则这个点是该图的一个"割点"

同理，如果删去一条边会使图的连通分量增加，这这条边是该图的一个"割边(桥)"

先思考一下什么时候一个点会成为割点

这里我们再引入一个值$low_i$指在不经过自己的父亲节点的情况下节点$i$最多经过一条非树边能到达的最小时间戳

因为时间戳是遍历的顺序，所以易得在任意一颗子树中根节点的时间戳一定最小

既然我们删去节点后连通分量会增加，那么说明割点的子树与其余部分不连通

所以如果该节点$p$的子节点$x$的$low_x \geq dfn_p$，那么这个节点$p$就是这个图的一个割点

但是有一个问题，对于我们遍历的根节点它是无法正常计算的，这时候我们只需要特判一下，如果它的儿子数量大于等于$2$则它也是一个割点

对于桥，照葫芦画瓢就行了，不过这次不能取等，因为分隔所得到的是两个点，如果取等可能会出现自边误判为桥的情况

这时候该节点$p$的子节点$x$的$low_x \gt dfn_p$则说明连接这两个节点的边是一个桥

但是要注意重边的情况，这时候可能存在一条相同结果的路径既是树边又是返祖边的情况，这种情况我们一般使用链式前向星存储或给边加上一个编号解决

void dfs( int p,int fa )//求割点的代码，DFS遍历树边
{
	vis[p]=true;//已经访问过该点，标记
	dfn[p]=low[p]=++idx;//打上时间戳(一个点能到达的最小时间戳最大就是本身)
	int son=0;//记录孩子数量用以特判
	for( auto x:rode[p] )//枚举所有的边
	{
		if( !vis[x] )//这是一条树边，走过去
		{
			son++;
			dfs( x,p );//继续递归
			low[p]=min( low[p],low[x] );//更新low
			if( p != fa && low[x] >= dfn[p] && !flag[p] ) flag[p]=true, ans++;//说明 p 是一个割点且删去 p 后以 x 为根的子树会独立(标记避免重复计算)
		}	
		else if( x != fa ) low[p]=min( low[p],dfn[x] );//这是一条横叉边/返祖边，更新low
	}
	if( p == fa && son >= 2 && !flag[p] ) flag[p]=true, ans++;//DFS的根，特判
}

void dfs( int p,int fa )//求桥的代码，DFS遍历所有树边
{
	bool flag=false;//标记重边
	vis[p]=true;//已经访问过该点，标记
	dfn[p]=low[p]=++idx;//打上时间戳(一个点能到达的最小时间戳最大就是本身)
	for( auto x:rode[p] )//枚举所有的边
	{
		if( !vis[x] )//这是一条树边，走过去
		{
			dfs( x,p );//继续递归
			low[p]=min( low[p],low[x] );//更新low
			if( low[x] > dfn[p] ) flag[p]=true, ans++;//说明连接 p 和 x 的这条边是桥
		}	
		else if( x != fa || flag ) low[p]=min( low[p],dfn[x] );//这是一条横叉边/返祖边，更新low
		else flag=true;//这是条重边，标记
	}
}

---

4.边双连通与点双连通分量

首先，我们先介绍一下边双连通与点双连通的定义：

在一个无向图中，如果删去图中的任意一个节点不会破坏节点$a$和$b$之间的连通性，即$a$和$b$之间有至少两条经过点不同(不重点)的路径，那么我们称$a$和$b$在这个图里面点双连通

同理，在一个无向图中，如果删去图中的任意一条边不会破坏节点$a$和$b$之间的连通性，即$a$和$b$之间有至少两条经过边不同(不重边)的路径，那么我们称$a$和$b$在这个图里面边双连通

如图，在这张图中，$1$和$2$点双连通且边双连通，$2$和$3$点双连通且边双连通，$1$和$3$边双连通

这样我们也还能找到一些规律：边双连通可传递而点双连通不行，因为点双连通的中间点可能就是一个割点

我们先来想一想怎么样去求边双连通分量，首先在无向图的$DFS$中不会存在横叉边

所以怎么样一些点对才不边双连通(连通图)，很简单就是两点间路径存在重边，这样删去重边后它们就不边双连通了对吧

那么对于其他的点，我们肯定会将它们划分在同一个边双连通分量里面(极大分量)，它们一块组成一个边双连通分量

嘶~~~，"两点间路径存在重边"不就是桥吗？

再理性思考一下，我们可以发现一个图一定可以划分为多个不重的边双连通分量，最差情况就是每个点单独成分量

想象一下把所有边双连通分量缩点，那么桥不就是连接不同边双连通分量的边吗

思路一下明晰了，我们只需要先求出原图的所有桥并标记，然后再一次$DFS$就可以求出原图的所有边双连通分量了(还是要记得重边的问题)

再考虑点双连通，这里也是一样，对于两个点双连通分量，我们可以发现它们至多有一个公共点且一定为割点

拓展一下，发现对于一个点双里的所有点，它的最小时间戳对应的点一定是(割点或树根)

所以我们发现如果一个点是割点，则它一定会被划分为一个点双连通分量的根，因为就算加上它的父亲它也依旧是割点

这时候就可以将访问的所有未划分进任意点双连通分量的点($dfn$大于割点)与这个割点划分进一个强连通分量了

但是当一个点为树根时，如果它不存在儿子则它自身需要被划分为一个单独的点双

void dfs( int p,int ine )//求边双的代码，DFS遍历所有树边
{
	dfn[p]=low[p]=++idx;//打上时间戳(一个点能到达的最小时间戳最大就是本身)
	for( auto [x,iidx]:rode[p] )//枚举所有的边
	{
		if( ine == iidx ) continue;//不能走相同的边，但是可以走重边
		if( !dfn[x] )//这是一条树边，走过去
		{
			dfs( x,iidx^1 );//继续递归(异或上1相当于访问这条边的另一个端点)
			low[p]=min( low[p],low[x] );//更新low
			if( low[x] > dfn[p] ) group[iidx]=group[iidx^1]=1;//说明连接 p 和 x 的这条边是桥，做好标记这条边是桥
		}	
		else low[p]=min( low[p],dfn[x] );//这是一条返祖边，更新low
	}
}

void get_ans( int p )//划分边双连通分量
{
	vis[p]=true;//已经访问过该点，标记(该点已经被划分进了一个边双)
	ans[num].push_back( p );//划分进一个边双里面
	for( auto [x,iidx]:rode[p] )//枚举所有的边
	{
		if( vis[x] ) continue;//已经被访问过，跳过(下一个点已经被划分进了一个边双)
		if( group[iidx] ) continue;//如果这是一条桥，则说明这是两个不同的边双，跳过
		get_ans( x );//继续递归
	}
}


for( int i=1, u, v;i<=m;i++ )//存储边时额外注意
{
	cin>>u>>v;
	rode[u].push_back( { v,i<<1 } ), rode[v].push_back( { u,i<<1|1 } );//多存储一维边的编号以处理重边问题
}

void dfs( int p,int fa )//求点双的代码，DFS遍历所有树边
{
	dfn[p]=low[p]=++idx;//打上时间戳(一个点能到达的最小时间戳最大就是本身)
	sta.push( p );//先将这个点压入栈中
	int son=0;//记录孩子数量用以特判
	for( auto x:rode[p] )
	{
		if( x == fa ) continue;//不能返回父亲
		if( !dfn[x] )//这是一条树边，走过去
		{
			son++;
			dfs( x,p );//继续递归
			low[p]=min( low[p],low[x] );//更新low
			if( low[x] >= dfn[p] )//点 p 就是一个割点
			{
				num++;//增加一个分量
				while( sta.top() != x ) ans[num].push_back( sta.top() ), sta.pop();//将所有时间戳更大的点加入这个强连通分量
				ans[num].push_back( sta.top() ), sta.pop();//要将 x 也pop出来
				ans[num].push_back( p );//要保留割点 p 因为它可能还会被划分在另一个点双之中
			}
		}	
		else low[p]=min( low[p],dfn[x] );////这是一条返祖边，更新low
	}
	if( p == fa && son == 0 ) ans[++num].push_back( p );//根单独的一个点划分为一个点双连通分量
}

5.圆方树

嗨嗨嗨，还是$Tarjan$发明的神奇数据结构

它是一种用来处理无向图的数据结构，它通过将一张图转化为一个树从而解决一些问题

圆方图常用在"仙人掌图"中，仙人掌图是指一个连通图且每条边只出现在至多一个环中，意思是不会存在一个边既出现在一个环中又出现在另一个环中

先举出一个情景：每次列出两个点，求它们之间有哪些割点(不是很严谨，尽量理解一下)

对于一个图，我们会先找出它的所有点双连通分量，然后将每个点双内部连接的边删去，然后新增一个节点，将它们全部连到这个节点上

如图

这时候我们可以得到：对于任意两点，它们之间的路径上的非新增点均是割点

对于这些新增的点，我们称之为方点，原来的称为圆点，每个点双成为一个以方点为中心的类菊花图，不同的"菊花图"之间通过割点相连

对于一个圆方树，我们易得以下性质：

<1>.树上只存在"圆圆边"和"圆方边"

<2>.每个方点对应了一个点双连通分量

<3>.方点的度是该点双的大小

<4>.只有圆点是割点时才有超过一个儿子(否则只连接着一个方点)

<5>.一个圆点至少连接一个方点，(割点)至多连接两个方点

注意在开存储圆方树的数组时要开两倍空间