Tarjan 系列学习笔记

最近在复习提高算法，所以学习复习笔记写的就比较多。

Tarjan 系列的算法主要针对于图论而言。

Part \(1\) 缩点

缩点算是 Tarjan 算法最广泛的应用了。

先讲拓扑序。在一个有向图中，若此图无环，我们称这个图是有向无环图，也叫 DAG，我们可以用拓扑排序解决许多图上问题，简单思路是先把入度为 \(0\) 的点丢进队列，再像 spfa 一样向四周扩散，每扩散一次就做对应操作（这里的操作是对于题目而言的），将扩散到的所有点的入度都减 \(1\)，直到某一个点入度变为 \(0\) 后再丢进队列，反复循环即可。

拓扑排序代码：

while(!q.empty()){
	a=q.front(),q.pop();
	for(int y:G[a]){
		p[y]+=p[a];//这里是你要做的操作
		ru[y]--;
		if(ru[y]==0) q.push(y);
	}
}

但是更多时候有向图是有环的，那怎么办呢？现在就引进缩点这一概念。

先给出一些定义：

1. 在有向图中，若点 \(u\) 和点 \(v\) 能相互到达，那么称点 \(u\) 与点 \(v\) 是强连通的。

2. 在一个有向图中，若任意点对都是强连通的，那么称这个图是个强连通图。

3. 在一个有向图中，极大的强连通子图称为是这个有向图的强连通分量。对于“极大”这一理解，就是任意加一个点 \(u\)，这个子图都无法构成强连通图。

那么 Tarjan 算法在这里的应用，就是把所有强连通分量缩成一个点，缩完后的新图是一个 DAG，相当于在缩点过程中把环都缩掉了。