Tarjan 算法学习笔记（超详细）
一、问题引入当你要求割点/割边/点双连通分量/边双连通分量/强连通分量的时候，它们都可以用一个算法来解决，而且代码差别不大，这个算法就是 Tarjan。
二、什么是强连通分量
对于一张有向图 \(S\) 的子图 \(V\)，满足 \(V\) 内的点两两之间可达，并且不存在一个子图 \(G\) 使得 \(G \supseteq V,G \not= V\)，通俗的讲就是无法继续扩张的两两可达的子图。
三、Tarjan 求强连通分量算法推导
首先对于一个有向图的搜索树中，它分为 \(4\) 种边：树边、返祖边、横叉边、前向边。树边就是搜索树中正常的边，返祖边就是一个点返回它的祖先的一条边，横叉边就是一个点连向了一个不是它的祖先也不是它的后代的点的这样一条边，前向边就是一个点连向它的后代（并非儿子）的边。
然后就是算法的流程，这个算法有两个数组 \(dfn\) 和 \(low\)，分别表示当前点的 \(\operatorname{dfs}\) 序和当前点所能到达的最小的 \(dfn\)，就跟并查集有点像，Tarjan 里的 \(low\) 数组就类似并查集里的 \(f\) 数组，首先根据搜索树的特性，对于任何一个强连通分量它们的点集在搜索树上的 \(dfn\) 是连续的，而且你会发现，任何一个强连通分量都有一个制高点 \(x\)（类似并查集找图的连通块时的根），使得 \(low_x = x\)，也就相当于找到了并查集中一个连通块的根，于是我们就有了一个大胆的猜想，先准备一个栈，存放着所有点，我们先在搜索时求出 \(low\) 数组和 \(dfn\) 数组，搜索时如果发现 \(low_x = x\)，说明找到了一个强连通分量的制高点，将强连通分量的数量加 \(1\)，同时将这个强连通分量从栈里删掉。
但是，我们会面临一个问题：如何求 \(low\)（\(dfn\) 是好求的）？
你可能会立马想到在搜索时，使用 \(low_x = \min(low_x,low_{son})\) 来求出 \(low\)，但是你会发现，这样不一定能得到正确的 \(low\)，因为你可能连向了一个点，而且你就是靠那个点更新 \(low\)，但是那个点还没搜完，你却搜完了，然后如果后面那个点的 \(low\) 又更新小了，但你却已经搜完，无法更新，但是……
真的有必要求出正确的 \(low\) 吗？
其实没必要。
因为我们的 \(low\) 它的作用其实只是找出强连通分量的制高点，也就是判断 \(low_x\) 是否等于 \(dfn_x\)，所以就算我们的 \(low\) 无法实时更新出正确的答案也不影响我们找到每个强连通分量的制高点。
证明？很简单！其实我们只需要证明两个东西就可以说明 \(low\) 值不准确也没关系，这两个东西分别是：如果正确的 \(low_x\) 等于 \(dfn_x\)，那么不准确的 \(low_x\) 也一定得等于 \(dfn_x\) 才行，你会发现这显然是对的，因为正确的 \(low_x\) 都连不向其它更小的点，那不准确的 \(low_x\) 更不可能连向其它更小的点，然后第二个要证明的事情就是如果正确的 \(low_x\) 不等于 \(dfn_x\)，那么不准确的 \(low_x\) 也一定得不等于 \(dfn_x\)，这个就有意思了，你想想不准确的 \(low_x\) 为什么不准确？那不就是因为 \(x\) 连向了一个点，但是 \(x\) 比那个点先搜完，那么后面如果那个点更新了那 \(low_x\) 就变得不准确了，但是这有关系吗？没有，因为我们已经连出去了才会出现 \(low_x\) 变得不准确，那我们都已经连出去了那肯定不准确的 \(low_x\) 就一定不等于 \(dfn_x\) 了。
然后再说一下，在搜索中遇到返祖边或目前没有被划入任何一个强连通分量的横叉边（前向边没用，因为指向的点已经被划分了）就不需要搜索，直接使用上述语句更新 \(low\)，如果是普通的树边就先搜索然后再更新 \(low\)，其它情况就什么都不用做。
四、Tarjan 求强连通分量板子
代码很简单，重要部分就几行。
#includeusing namespace std;const int N = ;//这里是数组大小，根据题目数据范围定vectora;//边集vectorg;//存每个强连通分量int cnt,scc_cnt,top;//分别表示目前的dfs序、当前找到几个强连通分量，栈顶int dfn,low;//跟上面说的dfn和low一样int scc_color;//表示每个点属于第几个强连通分量int sta;//栈void dfs(int x){ dfn = low = ++cnt;//先求出dfn，然后先给每个low赋一个初值 sta[++top] = x;//放入栈 for(int v:a) { //上面说的更新low的方法 if(!dfn) { dfs(v); low = min(low,low); } else if(!scc_color) { low = min(low,low); } } if(dfn == low)//找到制高点 { scc_cnt++;//强连通分量数量+1 int u; do { u = sta;//取出栈顶 scc_color = scc_cnt;//标记所属强连通分量编号 g.push_back(u);//在这个点所属的强连通分量里放入这个点 } while(u!=x);//因为对于任何一个强连通分量它们的点集在搜索树上的dfn是连续的，所以说从这个强连通分量的制低点（栈顶一定是这个强联通分量的制低点，这个原理很简单吧）删到制高点后就不能继续删了 }}int vis;signed main(){ int n,m; scanf("%d %d",&n,&m); for(int i = 1;i
页:
[1]