点击量：721

tarjan算法的大纲：

tarjan专题

最主要的分为两个板块，有向图和无向图

一、有向图

1.缩点、强连通分量 代码和注释

   如果在一个有向图中，任意两个节点可以互相到达，那么这些点和它们之间的边构成的图叫强连通分量，如果这些边没有边权，等价于一个点，如洛谷P2812 校园网络。如果这些点有点权，那么它们所缩成的点最大点权等于强连通分量中点权之和，见洛谷P3387 缩点。

   对于求强连通分量，我们由tarjan算法来实现。首先对每个没有遍历过的点为起点，进行dfs，每找到一个新点入栈一次，如果遍历到了已经遍历过的点，说明这个被二次遍历的点可以通过一个有向环回溯到自己。如果回溯所找到的时间戳小于自己所能回溯找到的最小时间戳（默认为自己的时间戳），那么将自己的回溯时间戳更新到更小。

   当dfs的递归回溯到自己时，将自己的回溯时间戳更新到子节点和自己中最小的一个，如果无法更新到比自己更小，说明自己是一个强连通分量的根结点，把栈中所有自己以上的点全部出栈，认为在同一个强连通分量中，根据题目需要进行处理。如果可以更新到更小，就把自己留在栈里，继续递归。

2.环

   在有向图中，我们一般找的是最小环，用一遍dfs就可以完成。不需要栈，只需要一个dfn数组。利用记忆化搜索的技巧，如果遍历到一个被搜过的点，它一定不能更新最小环为更小值，因为它的子树已经被遍历完了。在遍历过程中，用bfs序给各节点打上时间戳，就可以求出最小环的长度了。

二、无向图

1.树的最近公共祖先（lca）和树上点的距离

最近公共祖先详解   树上距离例题

   最近公共祖先（和树上距离）是可以通过倍增在$ O(NlogN)$时间内跳出来的，不过是离线算法。tarjan相比较更优，不仅是在线算法，而且一遍dfs复杂度只需要$ O(N)$。用到的技巧有并查集、前缀和等。在dfs过程中，对于一个子树的根结点，它的所有孩子与它自己的最近公共祖先都是它自己，所以先不把当前祖先更新到子树的根结点的父亲。等dfs结束后，子树内的询问处理完毕，其他点与这个点的最近公共祖先就一定不在这个子树里，将当前祖先向上更新一级，放到上面一级去回溯。这一找祖先的过程当节点关系不是直接父亲时需要用并查集来压缩路径。

   树上前缀和就是在dfs过程中存储各个节点到根结点的距离，如果在同一条链上就可以直接相减。而lca是一定与两个询问点分别和根结点“三点共链”的，因此可以快速求出两点之间的距离。

2.双连通分量

     ①点双连通分量、割点：代码解析

   在无向图中，对于一个分图，去掉其中任意一个点（及其有关边），其他各点仍然可以两两互达的分图叫做点双连通分量（包括一个点或两个相邻的点），往往处理一些割点问题。割点就是去掉后可以把一个连通图分为两个互不干扰的连通图。一张连通图上的所有割点，可以分这张图为多个双连通分量。

   割点的求法：特殊情况：对于一个有多孩子的根结点，它是一个割点。那么去掉这个点可分这棵树为一个森林，而如果只有一个孩子就不是森林了。   其他情况：如果一个点的孩子遍历完后，能回溯到的点不浅于这个点的时间戳（不能是回溯值，因为这个点可能属于另一端的双联通分量，可回溯过去），也就是low[son]>=dfn[x]，说明这个点是一个割点，我们可以理解为这个点将它下面的点封锁了。

   注意事项：在遍历过程中，双向边是可以访问到父亲的，但是要跳过，不然会乱了顺序。

     ②边双连通分量、割边/桥

   在无向图中，对于一个分图，去掉其中任意一条边，其他各点仍可以两两互达的分图叫边双连通分量。割边其实和割点是异曲同工的。因为删去割点，它附近的边也随之失效，就促成了割边。去掉割边，两侧互不干扰，但不一定为边双连通分量，而是连通图。

   割边的求法：没有特殊情况，所有情况和割点一般情况相同，在判断时需要稍作改动。因为割边两侧的点分属两个不同的区块，所以割边的一端（设为u）不能被另一端（设为v）的孩子遍历到，也就是回溯值不能小于v。因为我们是在递归过程中判断的，所以对于u，如果它的一棵子树的根结点的回溯值大于自己的时间戳（同样不能是回溯值），即low[v]>dfn[u]。那么这条连接u,v的边就是一条割边了。

   因为割点影响了边，而割边没有影响点，所以割边的两端一定都是割点，而割点所连的边不一定是割边。

3.缩点 例题解析

   无向图缩点可以同有向图一致，无向图只要不回溯到直接父亲，dfs序仍然是正确的，和有向图一样进栈找环就可以了。不过因为无向图单独一个点就是一个双连通分量，所以无向图中的环一般找最大环。

4.叶子连通块

   这是我在做一些tarjan题时想出来的一个概念，在一个连通图中，当所有割点/割边都删去（打上标记）时，对于每一个剩下的连通块，将其视作一个点，与割边或割点及其所连的边构成一个新图，此时可以保证新图是一棵树（环已经全部被缩掉了）。当这个点是叶子节点时，（叶子节点即入度为1的点），推导到这里来，叶子连通块也就是指只连接一个割点或一个割边的连通块。

   叶子连通块的性质：图中任意一个点或任意一条边被删掉，图中剩下的所有点都可以通过某种方式跑到叶子连通块处。这样就为我们求“维修、坍塌”类问题建模提供了方便。只要解决所有叶子连通块的需求，其他所有点的需求就迎刃而解了。所有的原因是，一旦某个叶子连通块被单独分开，它也要解决自己的需求。

例题1解析   例题2解析

三、总结

   各种算法都是同类算法中很优秀的算法，其中有一些异同的区分。

• 有向图、无向图都可以求环
• 有向图、无向图都可以缩点
• 缩点和求强/双连通分量时需要一个栈来存储；割点，割边则不用
• 割点去掉的是点和有关边，而割边只去掉了边。