Tarjan算法

我们先来了解一下Tarjan算法的作用Tarjan算法解决的是在有向图里找连通分量的问题连通分量听起来很高大上对吧但是实际上他就是一堆点它们两两之间可以互相到达像这样1 - 2 - 3 - 4 ^ | | | |--------------| 这里1,2,3,4就是一个连通分量因为从任意一个点出发都能绕一圈到达另一个点没错Tarjan实现的问题就是这么简单可是我们能用瞪眼法看出来但是机器做不到我们该怎么用一个高效的算法解决这个问题呢Tarjan算法的核心思想Tarjan用一次DFS就可以找连通分量我们DFS的时候会有两个很重要的编号我们在这里提前埋个伏笔dfn[u],low[u]它们非常的重要dfn[u]表示点u是第几个被访问到的如果通俗一点就是dfs序还是举一个例子吧假如说这棵树是这样的那么它的dfs序就是dfn[1]1 dfn[2]2 dfn[3]3 dfn[4]4 dfn[5]5我们理解了dfn[]之后需要理解low[]它十分重要。low[u]表示从u出发沿着dfs序往下走最多再通过一条返祖边能够到达的最早的dfn概念返祖边就是从图里抠出来了一颗树这棵树上有一个节点可以直接通过一条边连接到它的祖先哎呀其实说人话就是low[u]记录u或u的后代、最早能绕回哪一个祖先我们可以从这一张图片来理解low[u]看到这张图大众第一次看可能会觉得low[4]1实则不是的low[4]2因为是“最多通过一条返祖边”那么说到这里我们就可以开始学习新算法了我就问一个问题假如说有一个点u使得dfn[u]low[u]我们能不能确定它是某一个连通分量这里思路跳了实在想不出就继续看吧我们还是回到这个例子1 - 2 - 3 - 4 ^ | | | |--------------|从1开始DFS1访问2 2访问3 3访问4 4又能访问1于是dfn[1]1 dfn[2]2 dfn[3]3 dfn[4]4;但是4能回到1所以low[4]1然后3的儿子4能回到12的儿子3能通过4回到1所以low[2]1 low[3]1low[1]自己肯定是等于1的这个没啥好说的最后我们发现dfn[1]low[1]这真是一个惊天的发现这说明了1是这一整个连通分量里最早被访问到的点也就是一整个连通分量的“根”呃你就这么理解吧于是Tarjan就把栈从栈顶一直弹到1的点拿出来他们就是一个连通分量1,2,3,4懵逼的同学们太懵逼了不是这从哪里又冒出来一个栈啊其实是这样的DFS的过程中有点已经访问过了但是我们不知道它们属于哪一个连通分量所以Tarjan用一个栈保存这些“还没分组“的点访问一个点的时候把它压栈st[top]u; ins[u]true;其中有一个ins[u]表示u现在是否还在栈里当确定某个点u是连通分量的”根“也就是dfn[u]low[u]就开始弹栈while(true){ int xst[top--]; ins[x]false; id[x]scc; if(xu) break; }从栈顶一直弹到u为止这些点就是一个连通分量Tarjan的DFS过程所以Tarjan的核心代码就是这样的voidTarjan(intu){dfn[u]low[u]tm;st[top]u;ins[u]true;for(intv:g[u]){if(!dfn[v]){Tarjan(v);low[u]min(low[u],low[v]);}elseif(ins[v]){low[u]min(low[u],dfn[v]);}}if(dfn[u]low[u]){scc;while(true){intxst[top--];ins[x]false;id[x]scc;if(xu)break;}}}典例演习我这里有两道例题板子题你们可以拿来练练手反正我后面会出博客讲解https://www.luogu.com.cn/problem/P3387纯模板https://www.luogu.com.cn/problem/P2746挺有意思的一道题