强连通/缩点——dfs+并查集作法

2021年11月24日 阅读数:2
这篇文章主要向大家介绍强连通/缩点——dfs+并查集作法,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题外话

Trajan模板太难记了(对于我来讲),而后咱们教练就教了我一种dfs+并查集作法,感受挺容易理解,反正之后我就会使用这个模板了。code

前置芝士

强连通

若是有向图中的两个点可以互相到达,那么他们强连通。模板

强连通图

若是有向图中任意两点可以互相到达,那么这个图就是强连通图搜索

强连通份量

有向图中的极大强连通图子图就是强连通份量。(就是没有包含这个强连通子图的更大强连通子图)集合

缩点

把每一个强连通份量做为一个结点。co

正文

咱们可使用Trajan来实现缩点,网上文章大把,然而我喜欢用并查集作法。void

对于每一个强连通份量,咱们能够把它弄到一个并查集里面。文章

假设咱们如今dfs到一个点,它可能有三种状况:

  • 搜索完
    忽略,无论他。
  • 搜索中
    这时说明这两个点在同一个联通块里,用并查集合并。(至关于Trajan中的返祖边)
  • 未搜索
    咱们能够对这个点继续进行dfs。

注意在对两个节点进行并查集合并时,要把层数高的合并到层数低的,即以层数低的为根。

缩完点后,强连通份量的个数就是不一样祖先的个数。

一样咱们能够从新建边,只要这条边的两个节点不在同一强连通份量里咱们就能够连边。

核心代码就几行:

void dfs(int x)//DFS+并查集求强连通份量
{
	for(int g=h[x]; g; g=d[g].n)
	{
		int y=d[g].y; //当前节点是x,下一个节点是y
		if(!dep[y])
		{
			dep[y]=dep[x]+1; //用深度记录访问过
			dfs(y); //搜索下去
		}
		if(dep[fa(y)]>0) //若是y点在搜索中
		{
			if(dep[f[y]]<dep[fa(x)]) f[f[x]]=f[y]; 
			else f[f[y]]=f[x]; 
		}//合并x,y两个子图,要优先选深度小的为祖先
	}
	dep[x]=-1; //负数就是访问过
}