有关概念：
如果图中两个结点可以相互通达，则称两个结点强连通。
如果有向图G的每两个结点都强连通，称G是一个强连通图。
有向图的极大强连通子图（没有被其他强连通子图包含），称为强连通分量。（这个定义在百科上和别的大神的博客中不太一样，暂且采用百科上的定义）
Tarjan算法的功能就是求有向图中的强连通分量
思路：
定义DFNi存放访问到i结点的次序（时间戳），Lowi存放i结点及向i下方深搜到的结点中能追溯到的访问次序最小的结点的访问次序（即这些结点回溯上去能找到的最小的DFN值），找到未被访问过的结点时进栈，当找到一个强连通分量的根结点时（判断条件DFNi==Lowi），将该结点到栈顶之间的元素退栈，作为一个强连通分量
从结点1开始，枚举每一个未被访问的结点，以该节点为点u，进栈，赋DFNu=Lowu=time++，枚举每一个以u为起点的边，找到指向的终点v，进行判断：
（1）v未被访问过，则以v为起点继续深搜，并做Lowu=min(Lowu,Lowv)；
（2）v仍在栈内，则做Lowu=min(Lowu,DFNv)；（如果v的访问次序更小，更新Lowu，在回溯时更新u的父结点的Low值）
枚举完毕后，判断该结点是否为某一强连通分量的根节点，是则进行退栈操作
样例推导：
DFN={1,2,0,3,0,0}
搜索到4时有指向1的一条边，Low4=DFN1=1
6进栈
DFN={1,2,0,3,0,4}
判定 DFN6==Low6，6为第一个强连通分量的根节点，从6向栈顶（其实就一个元素）退栈，得第一个强连通分量为{6}
回溯到1，并更新Low值
DFN={1,2,0,3,0,4}
Low={1,1,0,1,0,4}
继续深搜到3，又有一条边指向4，Low3=DFN4=3
5进栈，有一条边指向6，但6被访问过且不在栈内，pass
此时5满足条件出栈，第二个强连通分量为{5}
回溯到1，更新Low值
DFN={1,2,5,3,6,4}
Low={1,1,3,1,6,4}
最后1满足条件，从1到栈顶出栈，第三个强连通分量为{1,2,3,4}
复杂度：
每一个点和边均只被访问过一次，时间复杂度为O(n+m)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN
#define MAXM
int n,m,time,cnt,heads[MAXN],DFN[MAXN],Low[MAXN],stack[MAXN],top,belong[MAXN];//time为访问次序，belong存该结点属于第几个强连通分量
bool vis[MAXN];//该结点是否在栈内
struct node
{
int v,next;
}edge[MAXM];
void add(int x,int y)
{
edge[++cnt].next=heads[x];
heads[x]=cnt;
edge[cnt].v=y;
}
void tarjan(int u)
{
DFN[u]=Low[u]=++time;
vis[u]=true;
stack[++top]=u;//进栈
for(int i=heads[u];i!=;i=edge[i].next)
{
int v=edge[i].v;
if(!DFN[v])//是否被访问过，DFN初值都为0，只有访问过才会被赋值
{
tarjan(v);
Low[u]=min(Low[u],Low[v]);
}
else if(vis[v])Low[u]=min(Low[u],DFN[v]);
}
if(DFN[u]==Low[u])//该结点为根结点，出栈
{
int i;
cnt++;
do
{
i=stack[top--];
vis[i]=false;
belong[i]=cnt;
print();//输出之类的操作
}while(u!=i);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);//默认输入有向边
}
cnt=;//cnt为强连通分量数量
for(int i=;i<=n;i++)
if(!DFN[i])tarjan(i);
return ;
}