tarjan算法，是一个可以在有向图中找到强连通分量的的算法。
首先你要了解什么是强连通，以及什么是强连通分量。
下面是我给的简释：
一、强连通。
就是在一个有向图（记为G）中，如果两个点（记为a，b）他们分别可以走到对方（即从a出发可以走到b，从b出发也可以走到a），那么我们说这两个点（a，b）是强连通的。
二、强连通子图。
设有一个有向图（记为G），他有一个子图（记为G1）,如果这个子图（G1）中的任意两点都是强连通的，那么我们就说这个子图（G1）叫做强连通子图。
三、强连通分量
极大的强连通子图。
解释：
强连通分量 百度百科
（这个百度百科上也有tarjan算法的介绍，还包括了其他几种算法）
好的，那么现在就有一个问题：
输入：一个图有向图。
输出：它每个强连通分量。
用tarjan算法怎么实现呢？
先给出几个变量的意义：
1.DFN[i]表示第几个搜索到的；
2.LOW[i]表示从搜索的路返回，最多能走到哪里。
3.STACK[i]表示一个栈。
输出了一个图，长这样：
怎么去找强联通分量呢？
xiam下面几张图是深搜的过程：（假设我们从第一个点开始搜）
搜到2，继续搜索2周围可以去的点，直到能去的点都去过了或者是没有能去的点了。
如下图：搜到6，走不动了，开始回溯。然后6出栈。6节点就是一个强连通分量。
于是 有了下图：回溯到3节点，操作不动了，3出栈。三就是一个强连通分量。
4走过了，于是继续操作至下图：
回溯到2，然后三走过，继续走5，五再继续操作，6走过且有DFN[6]!=LOW[6]，走1；
发现DFN[1]=LOW[1]
可以说明找到环了，就找到了一个强连通分量
于是我们继续找，如下图：
到5了之后，发现有LOW[5]=1;
LOW[4]=1;
然后还有一个栈内的搜索图，就是什么时候出栈，这个你可以自己画一下，就可以明白了。
然后最后栈里面剩下来的，就是所求的qian强连通分量。
好，下面以之前的那一道例题作为实战：（就是之前的那一道题）
输入n,m;
表示有n个点，m条边，下面输入m条边（单向边）；
输出所有的强连通分量。
下面是我自己的代码：
（你可以输入上面那个图验证）
#include<bits/stdc++.h>
using namespace std;
const int mm=1010;
vector<int>mat[mm];
int DFN[mm];
int LOW[mm];
int STACK[mm];
int visit[mm];
int tot,sta;
void tarjan(int x)
{
DFN[x]=LOW[x]=++tot;
STACK[++sta]=x;
visit[x]=1;
for(int i=0;i<mat[x].size();i++)
{
int v=mat[x][i];
if(DFN[v]==0)
{
tarjan(v);
LOW[x]=min(LOW[v],LOW[x]);
}
else if(visit[v]==1)
{
LOW[x]=min(LOW[x],DFN[v]);
}
}
if(DFN[x]==LOW[x])
{
while(x!=STACK[sta])
{
cout<<STACK[sta]<<' ';
visit[STACK[sta]]=0;
sta--;
}
cout<<x;
visit[x]=0;
sta--;
cout<<endl;
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
mat[u].push_back(v);
}
for(int i=1;i<=n;i++)
{
if(DFN[i]==0)
tarjan(i);
}
return 0;
}
推荐洛谷题目：
p3387