图的遍历(dfs)
强连通&强连通分量对于有向图G中的任意两个顶点u和v存在u->v的一条路径，同时也存在v->u的路径，我们则称这两个顶点强连通。以此类推，强连通分量就是某一个分量内各个顶点之间互相连通。
简单来说，就是有向图内的一个分量，其中的任意两个点之家可以互相到达。
求有向图内部强连通分量的方法大概有2种：tarjan算法，korasaju算法。这里我们只对tarjan算法进行讨论。
tarjan算法tarjan算法是tarjan神仙提出的基于dfs时间戳和堆栈的算法，这里我们可以先来看一下什么是dfs时间戳
dfs时间戳dfs时间戳就是dfs的先后顺序，详细来讲，比如我们dfs最先访问到的节点是A，于是A的时间戳就是1，第二个访问到的节点是E，那么E的时间戳就是2，我们用\(dfn[u]\)来表示u节点的时间戳，应该算是比较简单的
算法步骤首先，除了dfn以外我们还需要一个low数组，这个数组记录了某个点通过图上的边能回溯到的dfn值最小的节点。这句话相信在大多数博客里面都有提到，这里我们来看一个简单的例子：
首先，我们有一个图G:
假设我们从a点出发开始dfs，我们可以画出一个dfs树：
为什么我们画出来的dfs树和原来的图不一样呢？因为我们在dfs的过程中实际上是会忽略某一些连接到已访问节点的边的，这些边我们暂且称之为回边。对于点u来说，\(low[u]\)保存的就是点u通过某一条(或者是几条)回边能到达的dfn值最小的节点(也就是被最先访问的节点)。假设这个dfn值最小的节点是u'，我们可以知道，因为u和u'都是在一棵dfs树上的，并且u'可以到达u,同时u可以通过一条或多条回边到达u'，也就是说u'->u路径上的任意节点都可以通过这一条回边来互相到达，也就是说他们会形成一个强连通分量。
更加详细的例子我们有一个新图G:
假设我们从A点出发开始dfs，一路跑到D点，那么我们为这个图上的每一个点加上dfn数组和low数组的值（dfn,low），整个图就会长成这个样子：
此时我们会遇到一条D->A的回边，也就是说点D能访问到的dfn值最小的节点从点D本身变化到了A点，所以点D的low值就会发生相应的变化，\(low[D]=min(low[D],dfn[A])\)。
紧接着，dfs发生回溯，我们沿着之前的路径逐步更新路径上节点的low值，于是就有\(low[C]=min(low[C],low[D])\)，知道更新到某一个dfn值和low值相同的节点。因为这个节点能访问到的最小dfn的节点就是其本身，也就是说这个节点是整个scc最先被访问到的节点。
全部搞完大概会变成这个样子：
我们用一个辅助栈来保存dfs的路径，这样就可以在找到一个强连通分量里面最早被访问到的节点的时候可以输出路径。同时因为dfs访问是一条路走到黑的，所以可以保证栈内在节点u(low[u]==dfn[u])之前的的节点都是属于同一个scc的。
还是上面这幅图，我们顺便把E点给更新了：
跑完E点之后就会发现，E点本身的low就是和dfn相等的，所以此时栈内也只有E这一个节点。
于是上面这个图的scc有以下几个：
[E]
[A,B,C,D]
代码实现首先我们要发现，在dfs的初期我们每一个节点的low和dfn都是相同的，也就是说有dfn[u]=low[u]=++cnt（cnt为计数变量），并且在回溯的过程中要用后访问节点的low值来更新先访问节点的low值，也就是说有\(low[u]=min(low[u],low[v])\),当访问到某一个在栈中的节点的时候，我们要用这个节点的dfn值来更新其他节点，所以有\(low[u]=min(low[u],dfn[v])\)。