强连通分量 Tarjan 算法学习笔记

本文主要是介绍强连通分量 Tarjan 算法学习笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Part1. 强连通分量

强连通

我们知道，在无向图中，如果点 $u$ 和点 $v$ 直接或间接可以相互到达对方，就说点 $u$ ， $v$ 连通。

都可以说点 $1$ ， $2$ 是连通的。

但是在有向图中，能说点 $1$ ， $2$ 是连通的吗？

好像不太对，因为 $1$ 可以到达 $2$ ，但是 $2$ 不能到达 $1$ 。

这种情况，就说点 $1$ 点 $2$ 是弱连通的。

再看这张图：

此时，点 $1$ 点 $2$ 可以互相到达，我们说点 $1$ 点 $2$ 强连通。

强连通分量

无向图的连通分量就是图 $G$ 的一个子图，里面所有的点都是连通的。

所以有向图的强连通分量就是图 $G$ 的一个子图，里面所有的点都强连通。

上图中， ${1,2,3\}$ 是一个强连通分量， ${4\}$ 也是一个强连通分量。

整个图都强连通的图叫强连通图。

强连通分量的应用

有一些只能对 DAG 操作的算法，我们可以把所有强连通分量求出来，缩成点，此时的新图就是一个 DAG，就可以正常运行算法。

Part2. Tarjan 算法

Tarjan 算法是求强连通分量的算法，通过 $1$ 遍 dfs，可以求出所有的强连通分量。

【算法详细说明先咕咕咕，后续更新。】

Part3. 代码实现【模板】

void tarjan(int x){dfn[x]=low[x]=++ind;s.push(x);ins[x]=true;for(int i=head[x];i;i=e[i].nxt){int v=e[i].to;if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}else if(ins[v]){low[x]=min(low[x],dfn[v]);}}if(dfn[x]==low[x]){int v;ans++;do{v=s.top();ins[v]=false;s.pop();scc[ans].push_back(v);}while(v!=x);}
}