T a r j a n， 你真的了解吗？

# T a r j a n , 你真的了解吗 ？ **本文章有** - **关于tarjan的正确性证明** - **tarjan的思维模型推导** - **把tarjan应用于缩点** - **使用tarjan算法求割点&割桥** ------------ 读者须知： 1. 如果tarjan算法是干啥用的你都不知道，建议移步 [[洛谷日报第23期]初探tarjan算法 ](https://www.sohu.com/a/245954819_100201031) 1. 如果你学完了tarjan算法，却不知道为啥这是对的，恭喜你，接下来会一步一步剖析tarjan算法 1. 如果你~~和我刚学tarjan一样~~是一个连链式前向星或者邻接表都不会蒟蒻，请先打好图论基础，直接学tarjan真的非常没有效率和必要 ~~(劝退)~~ 1. 本文章全部采用链式前向星存图（链式前向星要比邻接表快了很多很多，~~被模板提卡时间的惨痛教训~~） ------------ # 一. TARJAN算法的正确性证明 为了防止刚进来的各位被我搞得云里雾里，先打个变量表 |变量名 |用处 | | :----------: | :----------: | |dfncnt |记录当前已经访问了几个节点 | |sccnum |记录当前已经有了几个强连通分量 | |dfn[ maxn ] |当前节点是第几个被访问到的 | | low[ maxn ] | 当前节点所能访问到的最小的 dfn[ ] | |scc[ maxn ] |记录各个节点所属于的强连通分量编号 | |s[ maxn ] |存储可能构成强连通分量的节点的栈 | |top |存储栈顶 | 唔似乎就这么多，下面会一个一个声明这几个数组的用处，所以看不懂也没事，放上代码（只求和下面的代码混个眼熟即可） ~~（当然你愿意敲一遍，那简直不胜荣幸）~~ ```cpp #include <iostream> #include <cstring> #include <queue> using namespace std; queue <int> q; const int Maxn = 1e4 +5, Maxm = 1e5 +5; int N, M; int head[Maxn], cnt = 1; int s[Maxn], top; int dfn[Maxn], low[Maxn], dfncnt, sccnum, scc[Maxn]; struct node{ int u, v, next; }G[Maxm]; void addedge(int u,int v){ G[cnt].v = v; G[cnt].u = u; G[cnt].next = head[u]; head[u] = cnt++; } void tarjan(int u){ low[u] = dfn[u] = ++dfncnt; s[++top] = u;//进栈 for (int i = head[u]; i ; i = G[i].next){ int v = G[i].v; if (!dfn[v]){ tarjan(v); low[u] = min(low[u], low[v]); } else if(!scc[v]){ low[u] = min(low[u], dfn[v]); } } if (low[u] == dfn[u]){ sccnum++; while(s[top] != u){ scc[s[top]] = sccnum; top--; } scc[s[top]] = sccnum; top--; } } int main(){ for (int i = 1; i <= N ; i++){ if(!dfn[i]) tarjan(i); } } ``` - 先理解一下各个变量的意义 ## scc[ maxn ] & sccnum : - 了解过tarjan的人一定知道sccnum是各个节点的强连通是 , 各个节点所属的强连通图的编号scc就是存储编号的数组 （注：强连通分量的英语缩写是scc） ## dfn[ u ] & low[ u ] : - dfn[ u ] 存储的是访问的顺序， low[ u ]存储的是访问的u点在强连通子图中最早被访问的点的编号， - **注意！！！low[ u ]是在u点所属的强连通子途中最早被访问的点的编号 , 即dfn编号** s[ maxn ] & top ： ------------ - 这是最重要的tarjan算法最重要的一环 , 思考：为什么是一个栈? A.tarjan想开一个栈，于是就开了一个栈。 ~~B.小孩子才做选择题，我全都要！~~ C.对于一个栈中的元素，后续入栈的点是他所有可能的，或许能够构成的强连通分量的集合 对，答案选C， 或许你没有看懂选项的意思，我来说明一下： 背景1 : **节点 u** 是**某个强连通分量的最早被访问的点** 背景2 :存在一条从u到v的路径，**当u被访问到时，v还未被访问到** 结合dfn[ u ] & low[ u ]的定义，推导出以下定理 1. 当我们判断是否 u 是一个强连通分量的最早被访问的点（即low[ u ]==dfn[ v ]）,我们一定已经遍历完了所有 u 能够到达的点 1. 结合背景2 和 定理1，一定有dfn[ v ] > dfn[ u ]，low[ v ] >= dfn[ u ] 1. 结合定理 2, 如果low[ v ] > dfn[ u ]，则 v 一定属于其他的强连通分量，又由于low[ v ] > dfn[ u ]，因此 v 所属的强连通分量的, **最早被访问的点 k**, **一定在u之后被访问到**，因此当回溯到u的时候，k一定早就被回溯到了，它所属的强连通分量一定已经被弹出 1. 我们可以通过定理2，推广到一切在u之后被访问到的所有强连通分量上去，所以当回溯到u的时候，在栈中所有不属于u强连通分量的点都已经被弹出了（严谨一点应该说在u之后入栈的，所有不属于u强连通分量的点都已经被弹出了） 1. 根据定理4，得出：当回溯到任意一个low[ u ] = dfn[ u ]时，从栈顶到u所处的位置所有的元素都是u的强连通分量 - **总结：** - 由于一个点进入栈时，接下来进入栈的点是**所有它能遍历的点**（除非那个点在栈内），他所属的强连通分量一定包含于它所能遍历到的点，因此，当遍历完一个点，他的强连通分量一定也被遍历了一遍 - 如果访问到**一个dfn有标记的点** 1. 这个点已经有了属于的强连通分量，那么这个点一定不属于当前栈内任何点的强连通分量 1. 这个点还没有属于的强连通分量，那么这个点一定在栈内（不在栈内的，有dfn序的一定都有所属的强连通分量，因为有dfn序意味着进过栈，有所属的强连通分量意味着已经出过栈） 1. 如果遍历到一个已经在栈内的点，该点可能是， 它在强连通图中，能访问到，最早被访问过的节点，去看一眼low[ u ]的定义，由于low[ u ]用于记录u点能找到的，最早被访问过的点的访问序列号，因此需要更新u点的 low【u】,即 ```cpp if(!scc[v] && dfn[v]){ low[u] = min(low[u], dfn[v]); } ``` - 如果访问到**一个dfn还没有标记的点** 1. 如下图，模拟一个栈，颜色代表所属的强连通分量  如果tarjan算法出现错误，则会有以下的可能： - 新入栈的元素所属的强连通分量，**中间插有其他的强连通分量**，如下图  这样显然是不可能的，之前已经证明过了，因为紫色块和绿色块的颜色不相同（它们属于不一样的强连通分量），所以紫色块显然到达不了绿色块（不然就不可能属于不同的强连通分量了），又因为在紫色块后入栈的点一定是紫色块能够到达的点，矛盾，因此不可能 - 弹栈不完全，即这个鬼样子  上面的绿色快还没有弹完就直接开始弹黄色块。这显然更加不可能了，只有low[ u ] == dfn[ u ]，才会进行弹栈的操作，如下图，low[ v ]!= dfn[ v ]的时候是不会进行弹栈的  - 说明 : 为了防止有人疑惑什么时候把low[ v ] 被更新成dfn[ u ]的，这里特别**再解释一下**：由于u和v强连通，则 v 一定会访问到 u ，（看tanjian我前面的解释），只有在访问完v的所有可以到达的节点才可能弹栈，因此v一定有机会更新成dfn[ u ]. - 求出的只是一张连通图，不是最大连通图（强连通分量） 这样显然也是不可能的，当开始弹栈的时候，我们一定已经遍历完了这个强连通图中每一个点的所有能够到达的点，一定都处于栈中 其他的出现错误我还没想到，如果各位有疑惑可以私信我，我会补充的 于是就有了以下代码 ```cpp for (int i = head[u]; i ; i = G[i].next){ int v = G[i].v; if (!dfn[v]){ tarjan(v); //说明v还未在栈中 low[u] = min(low[u], low[v]); } else if(!scc[v]){ low[u] = min(low[u], low[v]); } } ``` 这样子整体上的正确性证明就完成了，接下来只需要加上初始化点和弹栈的操作即可，就不再放代码了 # 二. TARJAN算法的思维模型 注意：此内容较为抽象，相比于tarjan算法本身并不重要，可以跳过 - 接下来将模拟~~tarjan老哥~~怎么想到求强连通分量的过程 - 在思考算法的时候需要先思考你要算的对象的性质，列举一下强连通分量的性质： - 如果存在一条u -> v的路径，同时也存在一条 v -> u 的路径，则u v两点连通 - 如果存在一条u -> v的路径，却不存在一条 v -> u 的路径，则u v两点不连通（这个反过来的性质很重要） - u的强连通分量的集合是指所有和u点互相连通的点的集合 遍历一张图的时候，我们要，求某一个点u，和它连通的所有的点，第一个想到的是dfs吧？（你想到bfs也没事，只要你想到了搜索就行）, 问题来了，即使v 和 u 有一条边，那也不一定会和 u 点连通啊，那怎么办？于是tarjan大佬想到了递归的思想： - 解决的问题具有通性：假设 u 和 v之间有一条边，继续遍历v所属的所有点，当遍历完后，如果发现 v 点已经有属于的强连通分量，那么 v 一定不会和 u 点相连通 。同理，对于v这个点之后遍历的所有点都可以这么做。 这里利用的是这么一条性质： - 如果存在一条u -> v的路径，却不存在一条 v -> u 的路径，则u v两点不连通 于是tarjan跨越了第一个难关，写出了这样的代码 ```cpp void tarjan(int u){ for(遍历u所有能够到达的点 v){ tarjan( v ); if(v点没有还没有强连通分量的话){ 把v 和 v 之后的，所有与 v 连通的点， 全部加入 u点所属于的强连通分量 的集合 } } if(u点能够构成强连通分量){ 记录u点能够构成强连通分量 } } ``` tarjan蜀黎很开心，他已经写出伪代码了！！！ 现在遇到第二个问题：什么情况下才会构成强连通分量？然后怎么才能把v和v之后的点全部加入u点所属于的强连通分量的集合？此时tarjan大佬想到了栈的思想： - 先进后出，后进后出：如果要是v点不属于u点的强连通分量，直接把v点弹出去就好 嗯现在还有一个问题：怎么能判断是否已经构成了强连通分量呢.........，看下面的性质 - 如果存在一条u -> v的路径，同时也存在一条 v -> u 的路径，则u v两点连通 唔，那么一旦v点遍历到u点，就一定说明 v 点和 u 点相连通喽？于是他进一步修改代码 ```cpp void tarjan(int u){ s[++top] = u;//因为是 u 所属的强连通分量，因此要把它入栈 for(遍历u所有能够到达的点 v){ if(v还没有被访问过{ tarjan( v ); if(v点没有构成强连通分量){ //或者说v点能够到达u点的话 //由于每一次tarjan（v）都会把 v和之后的点进栈 //又因为当v点构成强连通分量的时候会自然而然的出栈， //因此其实这一个判断是没有必要的 } } } if(u点和栈之后的元素已经是强连通分量){ 取出从栈顶到 u 的所有的点，这是u点的强连通分量 } } ``` 哇中间有一行判断居然没有必要，tarjan有点失落，但是他很高兴的是，算法的雏形已经要出来了！！！现在只剩下怎么弹出强连通分量了 怎么办呢？这里tarjan陷入了沉思 ~~（其实是我陷入了沉思）~~ ，当进行回溯的时候，回溯到哪一步的时候，能够判断已经是**强连通分量最早进入栈**的点了呢？ 哦，等等....最早进入栈的点....那也就是说我们只需要记录进入栈的时间么？这个简单，开一个数组 和 一个记录进栈次序的变量就好....但好像还不太够，即使我们拥有了次序，但是什么时候说明这是**这个强连通分量最早的进栈的点**呢.... 精彩的部分来了，Tarjan再一次利用了这个性质： - 如果存在一条u -> v的路径，却不存在一条 v -> u 的路径，则u v两点不连通 哦....似乎有什么闪过去了一下，是树....？树怎么了嘛...祖先！对，祖先！！只要记录这个点的祖先，这样这个点的儿子们，再次碰到这个祖先的时候就说明这两个点互相连通了！！！ 对，但是祖先应该记录什么时候的祖先呢？总不可能开一个好大好的数组存储每一个能够到达v点的祖先吧...这样比对的时候太浪费时间复杂度也太浪费空间复杂度了，得想想.... 当 v 的某一个子节点再次到达 v 的某一个父节点的时候,说明 v 和这个父节点连通喽。 那又怎么样？结合 我们刚刚设立的 访问次序数组....还有暂定的父节点数组...对哦，如果 v 的子节点 k 到达了某一个 v 的父节点 u ，证明这个从 v 一直到 v 的这个子节点全部是和这个父节点 u 连通的！！！ 因为在栈中的点进入栈次序早的一定能够到达进入栈次序晚的（在栈中的点一定能维持这一个性质，因为能够发现下图中，2这个点因为无法和1点连通，因此肯定已经出栈了，无法和1点连通的点全部都会被出栈）  为了保证强连通这个“最大的连通图的性质”，我们只需要记录某一个点所能达到的 进入栈顺序最小 的祖先（进入栈顺序大的祖先一定能被进入栈顺序小的祖先达到），每一次拿子节点所能达到的进入栈顺序最小的点去更新自己所能达到的进入栈顺序最小的点就可以了！！！ 等等，一桶凉水浇下来，即使能够知道在图中能找到的进入栈顺序最小的祖先，但是我们也没法判断什么时候是强连通图啊? 这个更简单了，不能忘记我们最开始的初衷：寻找强连通图中最早进入栈中的节点就好了。 那当一个节点，它所能达到的进入栈的次序最小点的点 = 它本身进入栈的次序时候，不就正好能够说明它是最早进入栈中的节点了嘛！！！ ~~（我很兴奋）~~ Tarjan很兴奋 总算结束了！！伪代码！！！ ```cpp int s[Maxn], top; int 次序变量，次序数组[Maxn],能达到的最小的次序数组[Maxn]; void tarjan(int u){ s[++top] = u;//因为是 u 所属的强连通分量，因此要把它入栈 次序数组[u] = 能达到的最小的次序数组[Maxn] = ++次序变量; for(遍历u所有能够到达的点 v){ if(v还没有被访问过){//此时次序数组[ v ]记录的是0 tarjan( v ); 能达到的最小的次序数组[u] = min(能达到的最小的次序数组[u],能达到的最小的次序数组[v]); } else if(v没有所属于的强连通分量){ //如果v被访问过了，且v没有所属于的强连通分量 //只能说明v在栈中，且一定是u的某一个祖先 达到的最小的次序数组[u] = min(能达到的最小的次序数组[u],次序数组[v]); } } if(u点能够构成强连通分量){ 取出，从栈顶到u的所有的点，这是u点的强连通分量 } } ``` 这里可以解答各位的一个疑惑了为什么这里 ```cpp for (int i = head[u]; i ; i = G[i].next){ int v = G[i].v; if (!dfn[v]){ tarjan(v); //说明v还未在栈中 low[u] = min(low[u], low[v]); } else if(!scc[v]){ low[u] = min(low[u], dfn[v]); } } } ``` 可以写成 ```cpp for (int i = head[u]; i ; i = G[i].next){ int v = G[i].v; if (!dfn[v]){ tarjan(v); //说明v还未在栈中 low[u] = min(low[u], low[v]); } else if(!scc[v]){//看这里 low[u] = min(low[u], low[v]); } } ``` 由于访问的是次序最小的节点，则low[ u ] 一定 = dfn[ u ] 好了这样就解决了 各位该喝水的喝水，该吃饭的吃饭，我已经写了7 8个小时了....建议各位稍微歇一会，再看下面的割点割桥 # 三. 缩点 所以搞到现在，tarjan算法有啥用，强连通分量有啥用？ 当然是有向无环图喽！！！ 看到这个缩点可以联想到什么吧？ 当然是把所有的环全部缩成一个点 给出两道例题 [P3387 缩点](https://www.luogu.org/problem/P3387) [P1073 最优贸易](https://www.luogu.org/problem/P1073) 可以先去看看是干嘛用的。 聊到有向无环图，一定就是topo了吧？ 现在整个算法的思路就出来了： 先用tarjan算法求出强连通分量，再建一个图 把各个环浓缩精华，变成新的图上的一个点 给出代码： ```cpp #include <iostream> #include <cstring> #include <queue> using namespace std; queue <int> q; const int Maxn = 1e4 +5, Maxm = 1e5 +5; int N, M; int head[Maxn], cnt = 1; int s[Maxn], top; int dfn[Maxn], low[Maxn], dfncnt, sccnum, scc[Maxn]; int d[Maxn], head2[Maxn], cnt2 = 1, ind[Maxn], dis[Maxn]; int t[Maxn]; struct node{ int u, v, next; }G[Maxm],G2[Maxm]; void addedge(int u,int v){ G[cnt].v = v; G[cnt].u = u; G[cnt].next = head[u]; head[u] = cnt++; } void addedge2(int u,int v){ G2[cnt2].v = v; G2[cnt2].next = head2[u]; ind[v]++; head2[u] = cnt2++; } void tarjan(int u){ low[u] = dfn[u] = ++dfncnt; s[++top] = u;//进栈 for(int i = head[u];i;i = G[i].next){ int v = G[i].v; if(!dfn[v]){ tarjan(v); low[u] = min(low[u], low[v]); } else if(!scc[v]){ low[u] = min(low[u], dfn[v]); } } if(low[u] == dfn[u]){ sccnum++; while(s[top] != u){ scc[s[top]] = sccnum; d[sccnum] += t[s[top]]; top--; } scc[s[top]] = sccnum; d[sccnum] += t[s[top]]; top--; } } void init(){ for(int i = 1; i <= M; i++){ int u = scc[G[i].u], v = scc[G[i].v]; if(u != v){ addedge2(u,v); } } } void topo(){ init(); for(int i = 1;i <= sccnum;i++){ if(ind[i] == 0){ q.push(i); dis[i] = d[i]; //cout<<d[i]<<endl; } } while(!q.empty()){ int u = q.front();q.pop(); for(int i = head2[u];i;i = G2[i].next){ int v = G2[i].v; ind[v]--; if(d[v] + dis[u] > dis[v]){ dis[v] = d[v] + dis[u]; } if(!ind[v]){ q.push(v); } } } } int t1, t2, t3; int main(){ cin>> N>> M; for (int i = 1;i <= N;i++){ cin>> t[i]; } for (int i = 1;i <= M;i++){ cin>> t1>> t2; addedge(t1,t2); } for (int i = 1;i <= N;i++){ if(!dfn[i])tarjan(i); } //cout<<sccnum<<endl; topo(); int ans=0; for (int i = 1;i <= sccnum;i++){ ans = max(ans,dis[i]); } cout<<ans; } ``` （当然你要是嫌我的代码难看可以自己手敲，记忆更深刻哦） # 四.割桥 和 割点 或许很多人有点疑惑...tarjan算法是不是应用于有向图呢...那无向图是不是也有“强连通分量”呢？ 很遗憾是没有滴，但是无向图有一个很有趣的东西，叫双连通分量，给出两种双连通的定义 - 点双连通：删去任何一个点仍然连通 - 边双连通：删去任何一条边仍然连通 （下面会简称为“点双和边双”） - 另一种定义是，任何两点之间至少存在**两条不经过相同中间点**（边）的路径 如果不满足双连通性 - 割点（割顶）：删去后原图不连通的顶点集合 - 点双连通：删去任何一个点仍然连通 - 边双连通：删去任何一条边仍然连通 - 割边（桥）：删去后原图不连通的边集合 - 边（点）双连通分量：删去所有割边（点），每个连通块都是双连通分量 - 一张图的边双连通分量之间可能有公共点，点双连通分量之间不可能有公共点  如上图， - 1，2，3，4，5，6，7是边双 - 1, 2 ,3, 4 是点双，4，5，6，7是点双 - 满足点（边）双连通性的极大子图称为点（边）双连通分量 这个时候就需要引出割点和割边的定义了： 如果一条边左边是一个最大的边双连通子图（边双），右边是另一个最大的边双连通子图（边双），那么这个边就是没有用的，删去，这样剩下的就是边双了  现在建议各位用tarjan的思路去想一想，试试看，边双该怎么办？ # 五.Tarjan算法优化 上面已经讲明白了基础的双连通的定义，下面就开始对Tarjan算法进行优化了，各位将要看到的是市面上没有的Tarjan算法改dfs求边双 嗯，还是应该是dfs吧？ 回忆一下边双的性质如果删去任何一条边，两个点就不能互相到达了，那么这个边不就是割桥么？ 那么继续之前的思路，dfn用来记录访问次序，low用来记录能够找到的最小的[ 节点的访问顺序 ], 如果没办法到前面的点，即low[v] > dfn[u],说明 v 没办法到达 u 之前的点，删去 给出代码： ```cpp int bcnt; int bnum[MAXN]; int dfncnt, dfn[MAXN], low[MAXN]; int s[MAXN], top = 0; inline void tarjan(int u, int fa) { dfn[u] = low[u] = ++dfncnt; s[top++] = now; bool flag = false;//判断两个节点中是否有多条边 for (int i = head[u]; i; i = G[i].next) { int v = G[i].v; if (v == fa && !flag) {//肯定是有一条边的 flag = true; continue; } if (!dfn[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); } else if (!bnum[v]) { low[u] = min(low[u], dfn[v]); } } if (low[u] == dfn[u]) { ++bcnt; do { bnum[s[--stop]] = bcnt; } while(s[stop] != u); }//内部的就全部是边双了 } ``` 割边就结束了 割点这里就有点麻烦了，看这个  由于一个点可能会属于多个点双（参考我们放上去的第一张图），因此点双并不好求，但是割点很好求，如果一个点是割点，那么删去这个点u的时候，一定会有一个点v，它到达不了dfn序 小于u的点（low[v] <= dfn[u]），同时，如果有多于两条树枝边，那么这就是割点 给出代码： ```cpp bool iscut[MAXN]; int dfncnt; int dfn[MAXN], low[MAXN]; inline void tarjan(int u, int rt) { dfn[u] = low[u] = ++dfncnt; int chcnt = 0;//根节点的子树个数 for (int i = head[u]; i; i = G[i].next){ int v = G[i].v ; if (!dfn[v]){ tarjan(v, rt); low[u] = min(low[u], low[v]); if (u == rt) chcnt++;//如果u是根节点的话 else if (low[v] >= dfn[u]) iscut[u] = 1;//说明v这个点回不去了 } else{ low[u] = min(low[u], dfn[v]); } } if (u == rt && chcnt >= 2) iscut[u] = 1; } ```