【算法笔记】Tarjan的SCC算法

前言

我爱 $\cy$ Tarjan！ Tarjan万岁！

（高中部的生活太美好，赛扩你high铁鸭子大~ $\cy$

一些基础

流图和搜索树

因为 $\text{Tarjan}$ 的 $\text{SCC}$ 算法是基于 $\text{dfs}$ 的。

所以需要一些关于“搜索树”的概念。

我们给定一张有向图 $G=(V,E)$。

如果存在一个 $r \in V$ ，使得从 $r$ 出发能够到达 $V$ 中其它的所有点。

那么我们称 $G$ 是一张“流图”，记作 $(G,r)$。

那么对于流图 $(G,r)$ ,我们对它进行 $\text{dfs}$，每个节点都只访问一次。

我们可以得到一颗搜索树 $T$ ，它就是这个流图 $(G,r)$ 的搜索树。

那么在 $(G,r)$ 的所有有向边 $(x,y) ,x \to y$ 中会出现这样子的四种情况：

树边：搜索树 $T$ 中的边。
正向边（前向边）：在搜索树中 $x$ 是 $y$ 的祖先节点。
反向边（后向边）：在搜索树中 $y$ 是 $x$ 的祖先节点。
交叉边（横叉边）：在搜索树过程中不同子树之间的边（也就是 $dfn[y] （\(dfn$ 是什么等会会说））。

这是一个流图 $(G,r)$ 和它的搜索树 $T$。

另外，在执行 $\text{dfs}$ 的过程当中，我们按照访问的次序以此给每一个节点 $u$ 打上一个标记 $dfn[u]$ （$dfn[u] \in N_+ \, ,\, dfn[u] \in [1,n]$）。

这个标记 $dfn$ 被称作“时间戳”。

强连通分量（Strongly Connected Component）

定义：

在有向图 $G$ 中，如果任意两个顶点都是连通的，那么这个图就是强连通图。

非强连通图的极大强连通子图，被称为强连通分量。

下图中的子图 $ {1,2,3,5}$ 就是一个极大强连通子图，子图 $\{4\}$ 也是一个极大强连通子图。

对于“极大”的理解，就是在一个局部子图中不能再大。

另外有一个理解：

每一个点都只能在一个 SCC 当中。

如果你一个点连接着两个不同的强连通分量（他们实际上应该是强连通子图）。

像下图那样，那么这两个强连通子图和这个点一定会构成一个新的更大的 SCC。

Tarjan的线性SCC算法

基础思想

你会发现，如果在 $G$ 当中出现了一个 “环”，那么这个“环”一定是一个强连通子图。

如果想要求强联通分量，那么我们就要尽可能地扩大这个强连通子图。

思考一下，如果要构成一个环，那么反向边是一定有用的，交叉边有时也有用（能在图 $G$ 中找到回到在搜索树中是祖先的节点的路的时候）。

所以 $\text{Tarjan}$的基本思路就是找到尽量多的环。

那么就需要找到反向边和交叉边，这时 $\text{Tarjan}$就引入了一个叫“追溯值 $low[u]$”的东西。

$low[u]$ 的定义：

$low[u]$ 是所有满足一下两个条件节点 $v$ 的最小时间戳的值。

这个点在搜索时建立的栈中（目前阶段被访问过了）
存在一条从 $u$ 的子树中出发的有向边，终点是这个节点 $v$

也就是以 $u$ 为起点，$u$ 或 $u$ 的子树能够追溯到的最早的栈中节点的 $dfn$。

说白了就是要尽量快地找到更多“环”。

至于这个栈是干什么的？

它在搜索时，边搜边记录所有当前阶段已经被访问过的节点。

用栈是为了符合 $\text{dfs}$ 的特点。

流程

当节点 $u$ 第一次被访问时，入栈，标记在栈里面。并且初始化 $low[u]=dfn[u]$
从 $u$ 出发，扫描所有出边 $(u,v)$
如果 $v$ 没有被访问过，那么 $(u,v)$ 是树边，递归去搜 $v$，回溯之后令 $low[u]=\min(low[u],low[v])$
反之，如果 $v$ 已经被访问过而且在栈之中，令 $low[u]=\min(low[u],dfn[v])$

（为什么是 $dfn[v]$ 请看 Tarjan 的论文，反正只能是这样子（有时不会出错但是不严谨））

然后如果 $low[u]=dfn[u]$ ，那么就找到了一个 $\text{SCC}$ ，记录，然后把栈中节点一直弹栈并加入 $\text{SCC}$ ,直到 $u$ 出栈（这里就可以看出来为什么要用栈）

$low[u]=dfn[u]$ ，也就是以 $u$ 为根的搜索子树的所有栈中节点能够到达的最早节点是 $u$ 本身。

为什么这个时候就一定是一个强连通分量了呢？

假设这个SCC里面有一个节点 $v$，但是它不属于 $u$ 为根的搜索子树的所有栈中节点所构成的集合 $S$。

那么也就是说在 $u \to v$ 的路径上面，一定有能够离开子树的一条反向边（去到比 $u$ 更早访问的节点），或者交叉边（从这个子树跳到另一个子树）。

这个边的终点的 $dfn$ 就必须比 $dfn[u]$ 小，和上面的条件：

“能够到达的最早节点是 $u$。”

矛盾了，那么此时无法构成SCC，所以这样的 $v$ 不存在。

那么很容易得知此时（$low[u]=dfn[u]$ ）已经构成了一个SCC。

Code：

（缩点 & SCC）


#include
using namespace std;

const int si_n=1e5+10;
const int si_m=1e6+10;
#define pb push_back

struct Edge{
	int ver,Next,head;
}e[si_m];
int cnt_e=0;
void add(int u,int v){
	e[++cnt_e].ver=v,e[cnt_e].Next=e[u].head;
	e[u].head=cnt_e;
}

stacks;
bool ins[si_n]; // in the stack or not
int c[si_n]; //c[x] = the num of SCC which is x iside
vectorscc[si_n]; // scc[i] -> all node in i-th scc (information of i-th scc)
int dfn[si_n],low[si_n];
int n,m,cnt_t=0,tot=0; // tot = how many scc in the graph. 

void tarjan(int u){
	dfn[u]=low[u]=++cnt_t;
	s.push(u),ins[u]=true;
	for(register int i=e[u].head;i;i=e[i].Next){
		int v=e[i].ver;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		++tot;
		int x;
		do{
			x=s.top(),s.pop(),ins[x]=false;
			c[x]=tot,scc[tot].pb(x);
		}while(u!=x);
	}
}

Edge edag[si_m];//新图
int cnt_d=0;
void add_n(int u,int v){
	edag[++cnt_d].ver=v,edag[cnt_d].Next=edag[u].head;
	edag[u].head=cnt_d;
}
void contract(){
	for(register int u=1;u<=n;++u){
		for(register int i=e[u].head;i;i=e[i].Next){
			int v=e[i].ver;
			if(c[u]==c[v]) continue;
			add_n(c[u],c[v]);
		}
	}
}//缩点

int main(){
	cin>>n>>m;
	for(register int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		add(u,v);
	}
	for(register int i=1;i<=n;++i){
		if(!dfn[i]) tarjan(i);
	}
	//......
}

注意在使用的时候可以视情况去掉 vectorscc 一类的东西来节省空间。

缩点就是直接把每一个 SCC 缩成一个新点（这时可以缩出一个DAG，建新图）

例题：

P3387 【模板】缩点
B3609 [图论与代数结构 701] 强连通分量
P2863 [USACO06JAN]The Cow Prom S

以上为模板题。

P2272 [ZJOI2007]最大半连通子图
P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G
P2921 [USACO08DEC]Trick or Treat on the Farm G
P3627 [APIO2009]抢掠计划
P2746 [USACO5.3]校园网Network of Schools
P2515 [HAOI2010]软件安装
P2403 [SDOI2010]所驼门王的宝藏
P3119 [USACO15JAN]Grass Cownoisseur G

Algor-强连通&amp双联通 Cate-图论 Type-算法笔记