在有向图G中，如果两个定点u，v间存在一条u到v的路径，也存在一条v到u的路径，则称u，v是强连通的。
若有向图G的任意两点都强联通，则称G是一个强联通图。
非强连通图的极大强连通子图称为强连通分量。
这里，极大强连通子图可以理解为一个子图是强连通图,且它的任意子图都不是强联通。
我们来看下面几张图。
这是强连通图。
这是强连通分量。
一个非强连通图中，可以有多个强连通分量。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~·
在考试中，遇到有强连通分量时，可以将他们缩成一个点，使原图其变成有向无环图（DAG），求解问题就方便了。
再看一个栗子：
这就很神奇了。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Tarjan算法
Tarjan算法主要是基于DFS搜索树。每一个强连通分量都是搜索树中的一颗紫薯子树
在利用数据结构——栈，将当前搜索树中未处理的节点入栈，回溯时即可判断是否构成强连通分量。
算法过程：
Tarjan算法需要维护两个数组：Dfn（节点被访问的时间，又叫时间戳），Low（回溯时能够回溯到最小的Dfn值）。
1.当首次遍历节点u时，dfn [ u ] = low [ u ] ;
2.u入栈，更新low [ u ];
3.遍历与u相邻的边（u , v）,
若v不在栈中，u是v的父节点，low [ u ] = min ( low [ u ] , low [ v ] );
若v在栈中， low [ u ] = min ( low [ u ] , dfn [ v ] )；
4.在u的子树都遍历完了之后，若low [ u ] = dfn [ u ],则栈顶到u之间（包括栈顶以及u）的元素组成了一个强连通分量。
5.继续搜索
让我们来手动模拟一下Tarjan
1.从0开始dfs
2.将顶点 0 的 dfn 0 和low 0 都设置为当前时间戳 1
3.接下来访问相邻未访问的顶点 1，将 dfn 1 和 low 1 都设置为当前时间戳 2。
4.接下来访问相邻未访问顶点 3，将dfn 3 和 low 3 都设置为当前时间戳 3
5.没有其他相邻顶点，此时 dfn 3 =low 3 ，故将 3 出栈作为一个强连通分量。
6.同样地，因为dfn 1 =low 1 ，所以将 1 出栈作为一个强连通分量。
7.继续访问和 0 相邻的其他顶点 2，将 dfn 2 和 low 2 都设置为当前的时间戳 4
8.访问相邻顶点 4，将 dfn 4 和 low 4 都设置为当前的时间戳 5。
9.访问相邻顶点 5，将 dfn 5 和low 5 都设置为当前的时间戳 6。
10.发现此时有指向栈中元素 1 的边，将 low 5 更新为 dfn 0 =1。
11.回溯到顶点 4，用low 5 更新low 4 ，更新为 1。
12.回溯到顶点 2，用 low 4 更新low 2 ，更新为 1。
13.顶点 2 有一个在栈中的相邻顶点 5，用 dfn 5 更新 low 2 ，不发生任何变化
14.回溯到顶点 0，用 low 2 更新 low 0 。此时发现 low 0 =dfn 0 ，将栈中元素弹出作为一个新的强连通分量。
15.找到下一个未访问的顶点 6，设置dfn 6 =low 6 =7。
16.发现顶点 6 没有指向栈中元素的边，搜索结束，将 6 作为一个新的强连通分量。
17.计算结束，{3},{1},{0,2,4,5},{6} 是图中的四个强连通分量。
好不容易，终于码完了。
那么，理解了思路，我们就来看看代码。
code of Tarjan：
1 stack<int>s; 2 int dfn[10001],low[10001],sum; 3 void tarjan(int u){ 4 dfn[u]=low[u]=++sum; 5 s.push(u); 6 visit[u]=true; 7 for(int i=head[u];~i;i=edg[i].nxt){ 8 if(!dfn[edg[i].to]){ 9 tarjan(edg[i].to); 10 low[u]=min(low[u],low[edg[i].to]); 11 } 12 else if(visit[edg[i].to])low[u]=min(low[u],dfn[edg[i].to]); 13 } 14 if(low[u]==dfn[u]){ 15 int j; 16 sumscc++; 17 do{ 18 j=s.top(); 19 s.pop(); 20 visit[j]=false; 21 scc[sumscc]++; 22 belong[j]=sumscc; 23 }while(j!=u); 24 } 25 }
这就是Tarjan算法，下次我们将通过习题再来深究Tarjan算法
祝大家NOIP rp++
