企业官网建设流程全解析

我们先来了解一下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开始DFS

1访问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能回到1，2的儿子3能通过4回到1，所以：

low[2]=1 low[3]=1

low[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 x=st[top--]; ins[x]=false; id[x]=scc; if(x==u) 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){intx=st[top--];ins[x]=false;id[x]=scc;if(x==u)break;}}}

典例演习：
我这里有两道例题（板子题），你们可以拿来练练手，反正我后面会出博客讲解：
https://www.luogu.com.cn/problem/P3387（纯模板）
https://www.luogu.com.cn/problem/P2746（挺有意思的一道题）