2019-07-25
luogu P2341 [HAOI2006]受欢迎的牛+Tarjan小复习
有向图强连通分量：在有向图GG中，如果两个顶点V_i,V_jVi?,Vj?间（V_i>V_jVi?>Vj?）有一条从V_iVi?到V_jVj?的有向路径，同时还有一条从V_iVi?到V_jVj?的有向路径，则称两个顶点强连通。如果有向图GG的每两个顶点都强连通，称GG是一个强连通图。有向图的极大强连通子图，称为强连通分量。 ——百度百科
事实上，你大概可以理解为：如果一个图的子图中，任意两点可以相互到达，那么这就组成了一个强联通分量。
如果还不理解怎么办？没关系，我们上图像来理解
如图，在这个有向图中，一共有\{1,2,3,4\},\{5\},\{6\}{1,2,3,4},{5},{6}三个强联通分量
我们需要两个非常重要的数组，在这里先说明一下
1.dfn1.dfn，表示这个点在dfsdfs时是第几个被搜到的。
2.low2.low，表示这个点以及其子孙节点连的所有点中dfndfn最小的值
3.stack3.stack，表示当前所有可能能构成是强连通分量的点。
4.vis4.vis，表示一个点是否在stackstack数组中。
我们使用tarjantarjan的方法 (1)、首先初始化dfn[u]=low[u]=dfn[u]=low[u]=第几个被dfsdfs到
(2)、将uu存入stack[ ]stack[]中，并将vis[u]vis[u]设为truetrue
(3)、遍历uu的每一个能到的点，如果这个点dfn[ ]dfn[]为00，即仍未访问过，那么就对点vv进行dfsdfs，然后low[u]=min\{low[u],low[v]\}low[u]=min{low[u],low[v]}
(4)、假设我们已经dfsdfs完了uu的所有的子树那么之后无论我们再怎么dfsdfs，uu点的lowlow值已经不会再变了。
至此，tarjantarjan完美结束
那么如果dfn[u]=low[u]dfn[u]=low[u]这说明了什么呢？
再结合一下dfndfn和lowlow的定义来看看吧
dfndfn表示uu点被dfsdfs到的时间，lowlow表示uu和uu所有的子树所能到达的点中dfndfn最小的。
这说明了uu点及uu点之下的所有子节点没有边是指向u的祖先的了，即我们之前说的uu点与它的子孙节点构成了一个最大的强连通图即强连通分量
此时我们得到了一个强连通分量，把所有的u点以后压入栈中的点和u点一并弹出，将它们的vis[ ]vis[]置为falsefalse，如有需要也可以给它们打上相同标记（同一个数字）
Q:Q: dfndfn可以理解，但为什么lowlow也要这么做呢？
A:A:因为low的定义如上，也就是说如果没有子孙与u的祖先相连的话，dfn[u]dfn[u]一定是它和它的所有子孙中dfndfn最小的（因为它的所有子孙一定比他后搜到）。
Q:Q: stack[]stack[]有什么用？
A:A:如果uu在stackstack中，uu之后的所有点在uu被回溯到时uu和栈中所有在它之后的点都构成强连通分量。
Q:Q: low[ ]low[]有什么用？
A:A:应该能看出来吧，就是记录一个点它最大能连通到哪个祖先节点（当然包括自己）
如果遍历到的这个点已经被遍历到了，那么看它当前有没有在stack[ ]stack[]里,如果有那么low[u]=min\{low[u],low[v]\}low[u]=min{low[u],low[v]}
如果已经被弹掉了，说明无论如何这个点也不能与uu构成强连通分量，因为它不能到达uu
如果还在栈里，说明这个点肯定能到达uu，同样uu能到达他，他俩强联通。
接下来，就是非(sang)(sang)常(xin)(xin)简(bing)(bing)单(kuang)(kuang)的手\%%过程了
从节点11开始DFSDFS，把遍历到的节点加入栈中。搜索到节点u=6u=6时，DFN[6]=LOW[6]DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=vu=v为止，\{6\}{6}为一个强连通分量。
之后返回节点55,发现DFN[5]=LOW[5]DFN[5]=LOW[5]，于是我们又找到了一个新的强联通分量\{5\}{5}
返回节点33，继续搜索到节点44，把44加入堆栈。发现节点44向节点11有后向边，节点11还在栈中，所以LOW[4]=1LOW[4]=1。节点66已经出栈，(4,6)(4,6)是横叉边，返回33，(3,4)(3,4)为树枝边，所以LOW[3]=LOW[4]=1LOW[3]=LOW[4]=1。
继续回到节点11，最后访问节点22。访问边(2,4)(2,4)，44还在栈中，所以LOW[2]=DFN[4]=5LOW[2]=DFN[4]=5。返回11后，发现DFN[1]=LOW[1]DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量\{1,3,4,2\}{1,3,4,2}。
至此，tarjantarjan算法结束，我们找到了全部的33个强联通分量\{1,2,3,4\},\{5\},\{6\}{1,2,3,4},{5},{6}
以下代码实现：
inline int tarjan(int u)
{
low[u]=dfn[u]=++dfn_sum;
stack[top++]=u;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(dfn(v))
low[u]=min(low[u],dfn[v]);
else
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
}
if(low[u]==dfn[u])
{
int now=stack[--top];s_sum++;
s[u]+=s_sum;
while(now!=u)
{
s[now]=s_num;
now=s[--top];
}
}
}
2019-07-25 23:38:32
未完
原文：https://www.cnblogs.com/plzplz/p/11247732.html