Introduction
Tarjan算法是用于寻找图中强连通组件的高效算法。通常叫做「割点」或者「割边」，也叫做桥，也就是说如果去掉了某个节点，或者某条边，图中的连通分量数量会增加，那么这样的节点就是割点，这样的边就是桥。
比如说，下面这个图中的节点2就是一个「割点」：
而下面这个图中的红色的边就是「桥」：
Tarjan’s Algorithm
寻找「割点」和「桥」的朴素方法是，遍历每一个节点，或者边，尝试去掉它，然后查看连通分量的数量有没有增加，显然这样复杂度很高至少是O(n2)的，所以要介绍一个常用的算法：Tarjan。
为了简单，假定图的节点为0~n-1，需要两个辅助数组disc[n]用以表示每个节点被访问到的次序，或者说被访问到的时间戳，需要注意，这个对于图中节点来说是唯一的，且与每个节点是一一对应的，代表着遍历过程中访问到每个节点的次序。目的是用于唯一标识每个节点，以及节点在遍历中的次序。
另一个辅助数组是low[n]，它记录的是当前节点所在的子树中被访问到的最早的节点，也就是强连通分量子树的根。也就是说low[u]的值是包含u在内的子树的根，它一定是最早被访问的。原理在于，强连通分量一定有环，那么从当前节点u再往回返回到的u之前的节点时，就形成了环，也即是连通分量，low[u]就记录着这个连通分量的根，也即最早被访问到的节点。显然，当low[u] = u时，就找到了这个根节点，当然也找到了一个强连通分量，如果在遍历过程中记录顶点，那么当low[u] = u时，记录过的顶点就都在一个强连通分量里面。
需要注意的是，这里遍历的方法要用DFS，因为DFS肯定能以最快的方式找到环，回到已遍历过的节点。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 1192. 查找集群内的关键连接 | 题解 | 板子题 |
| 题解 | ||
| 题解 |
关联知识
强连通分量，强连通分量是指图中的一组相互均可达的节点组成的子集。注意，强连通分量里面的节点，只需要相互均可达，并不要求直接有边连接。
不同的强连通分量之间的连接（即边或者顶点）即是「割点」和「桥」。
寻找强连通分量的算法，除了Tarjan以外，还有Kosaraju算法。