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

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15569521.html

题外话

Trajan模板太难记了（对于我来说），然后我们教练就教了我一种dfs+并查集做法，感觉挺容易理解，反正以后我就会使用这个模板了。

前置芝士

强连通

如果有向图中的两个点能够互相到达，那么他们强连通。

强连通图

如果有向图中任意两点能够互相到达，那么这个图就是强连通图

强连通分量

有向图中的极大强连通图子图就是强连通分量。（就是没有包含这个强连通子图的更大强连通子图）

缩点

把每个强连通分量作为一个结点。

正文

我们可以使用Trajan来实现缩点，网上文章大把，然而我喜欢用并查集做法。

对于每个强连通分量，我们可以把它弄到一个并查集里面。

假设我们现在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; //负数就是访问过
}