对Tarjan算法复习总结

《对Tarjan算法复习总结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、MTarjan算法的总结xy4hswjyyyO、tarjan算法的大纲厂有向图1•缩点tarjan<〔2.强连通分量二＞3.环树二＞4./ca无向图2桥/害ij边二＞5•边双连通分量割点二＞6•点双连通分量I7缩点tarjan专题这是我在博客里整理的有关tarjan的内容。最主要的分为两个板块，有向图和无向图一、有向图1•缩点、强连通分量代码和注释如果在一个有向图中，任意两个节点可以互相到达，那么这些点和它们之间的边构成的图叫强连通分量，如果这些边没有边权，等价于一个点，如洛谷P2812校园网络。如果这些点有点权，那么

2、它们所缩成的点最大点权等于强连通分量中点权之和，见洛谷P3387缩点。对于求强连通分量，我们由tarjan算法来实现。首先对每个没有遍历过的点为起点，进行dfs,每找到一个新点入栈一次,如果遍历到了已经遍历过的点,说明这个被二次遍历的点可以通过一个有向环回溯到自己。如果回溯所找到的时间戳小于自己所能回溯找到的最小时间戳（默认为自己的时间戳），那么将自己的回溯时间戳更新到更小。当dfs的递归回溯到自己时，将自己的回溯时间戳更新到子节点和自己中最小的一个，如果无法更新到比自己更小，说明自己是一个强连通分量的根结点，把栈中所

3、有自己以上的点全部出栈，认为在同一个强连通分量中，根据题目需要进行处理。如果可以更新到更小，就把自己留在栈里，继续递归。2•环在有向图中，我们一般找的是最小环，用一遍dfs就可以完成。不需要栈，只需要一个dfn数组。利用记忆化搜索的技巧，如果遍历到一个被搜过的点，它一定不能更新最小环为更小值，因为它的子树已经被遍历完了。在遍历过程中，用bfs序给各节点打上时间戳，就可以求出最小环的长度了。二、无向图1.树的最近公共祖先（lea）和树上点的距离最近公共祖先详解树上距离例题最近公共祖先（和树上距离）是可以通过倍增在0（Nl

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

5、，如果在同一条链上就可以直接相减。而lea是一定与两个询问点分别和根结点“三点共链”的，因此可以快速求出两点之间的距离。1.双连通分・①点双连通分量、割点：代码解析在无向图中，对于一个分图，去掉其中任意一个点（及其有关边），其他各点仍然可以两两互达的分图叫做点双连通分量（包括一个点或两个相邻的点），往往处理一些割点问题。割点就是去掉后可以把一个连通图分为两个互不干扰的连通图。一张连通图上的所有割点，可以分这张图为多个双连通分量。割点的求法：特殊情况：对于一个有多孩子的根结点，它是一个割点。那么去掉这个点可分这棵树为一个

6、森林，而如果只有一个孩子就不是森林了。其他情况：如果一个点的孩子遍历完后，能回溯到的点不浅于这个点的时间戳（不能是回溯值，因为这个点可能属于另一端的双联通分量，可回溯过去），也就是low[son]>=dfn[x],说明这个点是一个割点，我们可以理解为这个点将它下面的点封锁了。注意事项：在遍历过程中，双向边是可以访问到父亲的，但是要跳过，不然会乱了顺序。②边双连通分量、割边/桥在无向图中，对于一个分图，去掉其中任意一条边，其他各点仍可以两两互达的分图叫边双连通分量。割边其实和割点是异曲同工的。因为删去割点，它附近的边也随

7、之失效，就促成了割边。去掉割边，两侧互不干扰，但不一定为边双连通分量，而是连通图。割边的求法：没有特殊情况，所有情况和割点一般情况相同，在判断时需要稍作改动。因为割边两侧的点分属两个不同的区块，所以割边的一端（设为U）不能被另一端（设为V）的孩子遍历到，也就是回溯值不能小于V。因为我们是在递归过程中判断的，所以对于U,如果它的一棵子树的根结点的回溯值大于自己的时间戳（同样不能是回溯值），即low[v]>dfn[u]0那么这条连接u,v的边就是一条割边了。因为割点影响了边，而割边没有影响点，所以割边的两端一定都是割点，而

8、割点所连的边不一定是割边。1.缩点例题解析无向图缩点可以同有向图一致，无向图只要不回溯到直接父亲，dfs序仍然是正确的，和有向图一样进栈找环就可以了。不过因为无向图单独一个点就是一个双连通分量，所以无向图中的环一般找最大环。2.叶子连通块这是我在做一些ta「jan题时想出来的一个概念，在一个连通图中，当所有割点/割边都删去（打上标