强连通分量：Kosaraju 与 Tarjan

前言

在有向图 $G$ 中，如果两个顶点 $v_i,v_j$ 间有一条从 $v_i$ 到 $v_j$ 的有向路径，同时还有一条从 $v_j$ 到 $v_i$ 的有向路径，则称两个顶点强连通 (strongly connected) 。

如果有向图 $G$ 的每两个顶点都强连通，称 $G$ 是一个强连通图。

有向图的极大强连通子图，称为强连通分量。

Kosaraju 算法

Kosaraju 算法（也称为 Kosaraju-Sharir 算法）是线性时间的算法来找到一个有向图的强连通分量。

这个算法利用了一个事实，即转置图（同图中的每边的方向相反）具有和原图完全一样的强连通分量。

Kosaraju 算法比较关键的部分是同时应用了原图 $G$ 和反图 $GT$ 。

首先，在原图 $G$ 上第一次深搜遍历时，记录时间 i 离开的顶点 j ，即 numb[i]=j （当然，也可以记录第 j 个顶点离开的时间 i ）。

接着，每一次循环我们需要找到没有找过的顶点中具有最晚离开时间的顶点进行深搜（对于 $GT$ 来说）。每次深搜都得到一个强连通分量。

隐藏性质:

我们注意到第二次深搜选择树的顺序有一个特点：如果把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。

（注：在一个有向无环图中，所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列 (Topological order) 。）

实现思路：

首先，在原图上进行 DFS ，保存每个结点的离开时间。
接着，在反图上，找到刚刚保存的具有最晚离开时间的结点，并从此结点开始 DFS ，此时遍历到的即为一个强联通分量。
然后，删去刚刚遍历到的点，再一次重复上一步骤，直到所有点都被删去。

由于算法的时间取决于两次 DFS ，因此时间复杂度，对于稀疏图是 O(V+E) ，对于稠密图是 O(V^2) ，可见这是一个线性算法。

Tarjan 算法

Tarjan 算法主要需要维护以下三个信息：

一个栈，用于记录当前已经访问过但是还没有被归类到任意强连通分量的节点。
dfn[u] ，表示点 $u$ 的 DFS 序（第一次出现的时间），即标记点 $u$ 是第几个被 DFS 到的点（前置知识：DFS 树）。
low[u] ，从 $u$ 或者以 $u$ 为根的子树中的结点出发通过一条返祖边或者横叉边可以到达的时间戳最小的，且能够到达 $u$ 的结点 $v$ 的时间戳

low[] 的计算方法：

假设当前正在对点 $u$ 做 DFS 且正在处理一条从 $u$ 向 $v$ 的边。

若点 $v$ 还没有被搜索过，那么这条边为树边，此时有 low[u]=min(low[u],low[v]) ，也就是将这一次走非树边的机会留给子树。
若这条边是一条返祖边（返祖边一定满足条件）或满足条件的横叉边，那么有 low[u]=min(low[u],dfn[v]) ，将这一次走非树边的机会用掉。
若这条边是一条向前边，那么根据定义，它对 low[u] 的计算是没有影响的。

强连通分量的根的判定：dfn[u]==low[u] 。此时，需要将整个强连通分量从栈中弹出。

判断横叉边是否符合条件：v 在栈里。

例题：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

//洛谷 P2341 [HAOI2006]受欢迎的牛

int read()
{
	int x=0;
	bool f=false;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=true;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?-x:x;
}

int n,m;
int to[50005],nxt[50005],first[10005];
int col,num;
int dfn[10005],low[10005],de[10005],si[10005];
int tot;
int co[10005];
int top;
int st[10005];
int ans;

void add(int x,int y)
{
	to[++tot]=y;
	nxt[tot]=first[x];
	first[x]=tot;
}

void Tarjan(int u)
{
	dfn[u]=low[u]=++num;
	st[++top]=u;
	for(int i=first[u];i;i=nxt[i])
	{
		int v=to[i];
		if(!dfn[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!co[v])
				low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		co[u]=++col;
		++si[col];
		while(st[top]!=u)
		{
			++si[col];
			co[st[top]]=col;
			--top;
		}
		--top;
	}
}

int main()
{
	n=read();
	m=read();
	for(int i=1;i<=m;i++)
		add(read(),read());
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			Tarjan(i);
	for(int i=1;i<=n;i++)
		for(int j=first[i];j;j=nxt[j])
			if(co[i]!=co[to[j]])
				de[co[i]]++;
	int u=0;
	for(int i=1;i<=col;i++)
		if(!de[i])
		{
			ans=si[i];
			u++;
		}
	if(u==1)
		printf("%d",ans);
	else
		printf("0");
	return 0;
}

注：部分资料来源于百度百科

参考资料：

【R9OI】Tarjan 算法及其应用 https://www.bilibili.com/video/BV1ya411M7T

前言

Kosaraju 算法

Tarjan 算法

继续读