打算开始重新复习一遍相关算法。对于有向图tarjan算法，通过学习过很多说法，结合自己的理解，下面给出算法自己的观点。
算法总模型是一个dfs，结合一个stack（存放当前尚未形成SCC的点集合），记录下俩个数组：
dfn【i】:结点i的访问时间戳。 low[i]:i结点所能到达的祖先。
主要是俩次对low【u】的更新，一次：回溯的时候，u的孩子结点（vv）对u的更新，
if(low[vv]<low[u])low[u]=low[vv]; //孩子可以到达，我必然也可以到达。
二次：
if(dfn[vv]<low[u])low[u]=dfn[vv]; //能到达的祖先，所以更新。这里“祖先”，表面上看是孩子，其实是某个祖先结点。
若每次访问对u的孩字访问结束：若u满足
if(dfn[u]==low[u])则 以u为根，stack中u以及u上的点必然形成以个SCC。
个人证明如下：
1.u必然可以到达u的所有孩子，此时就是栈中u之上的点。这个毋庸置疑。
2.下面只需证明所有孩子都可以到达u:
对任意点（stack中在u之上的） i，必有dfn[i]>low[i],（若相等必然已经弹栈），i到达low[i]=dfn[j]<low[j]=dfn[k]<low[p].......，一直递减，其中i,j,k，p...代表不断找可达的祖先，
知道到u为止（递减有下界），所以任意结点都可以到u。
即证明了是u以上已经u是一个SCC。
额外说明几点（易误点）：
1,：low值相同的点一定在同一个scc中，毋庸置疑的这个。
2：同一个SCC中的点的LOW值未必都相同，是因为更新有先后的问题（可以举例）。但是除根外，其他点dfn>low，这个显然。
对于无向图，只需要把边改为双向边即可，这时候，（无向图详细待更新）。
hdu1269题意：判断有向图是否是强连通。直接用tarjan算法即可，只有一个SCC（强连通分量）。
给出核心代码已经详见：（有向图涉及强连通的，要用栈）
void tarjan(int u)
{
dfn[u]=low[u]=++times; //时间戳的标记
instack[u]=1;
s.push(u);
for(int i=0;i<v[u].size();i++)
{
int vv=v[u][i];
if(!vis[vv])
{
vis[vv]=1;
tarjan(vv);
if(low[vv]<low[u])low[u]=low[vv]; //孩子可以到达，我必然也可以到达。
}
else if(instack[vv]) //注意，更新时要有在栈中条件，代表该孩子（其实是祖先）我能到达，而且是属于当前SCC。
{
if(dfn[vv]<low[u])low[u]=dfn[vv]; //能到达的祖先，所以更新。
}
}
if(dfn[u]==low[u]) //是一个scc的根节点，出栈，一发现就出栈。
{ int cur;num++
do
{
cur=s.top();
s.pop();
instack[cur]=0; SCC[cur]=num; //这里可以完成缩点工作。
}while(cur!=u);
}
}
有向图tarjan算法求连通分量的粗浅讲解、证明， // hdu1269,布布扣,bubuko.com
有向图tarjan算法求连通分量的粗浅讲解、证明， // hdu1269
原文：http://blog.csdn.net/u011498819/article/details/24180791