第一篇博客，尽管园龄已经一年了。。
tarjan算法求强连通分量
有种tarjan算法是求强连通分量的。
那强连通分量是啥呢？
在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。
（如还不懂就点这）
such as：
该图中共有三个强连通分量，分别为【1,2,3,4】、【5】、【6】。
1,2,3,4之间可以相互到达，而5和6只能到达自己，所以分成了以上三个分量。
要找强连通分量，使用链表与深搜结合的办法：
建好表后，以每一个点为起点都深搜一次，这里需要维护两个数组，一个是dfn[N]，一个是low[N]。
dfn[v]表示顶点v被访问的时间，low[v]表示与顶点v邻接的未删除的顶点u的low[v]与low[u]的最小值。
在深搜的回溯过程中，如果dfn[v]==low[v]，那么当前顶点就是一个强连通分量的根（由于不断维护low数组，所以该强连通分量中所有节点的low都为第一遍深搜时时间。如果不是强连通分量的根，那么一定属于另一个强连通分量，而且它的根是当前顶点的祖宗,那么存在包含当前顶点的到其祖宗的回路，可知low[v]一定会被更改为一个比dfn[v]更小的值）
下附代码
1 #include<cstdio> 2 #include<stack> 3 #define N 420000 4 using namespace std; 5 stack<int>p; 6 struct hehe{ 7 int next; 8 int to; 9 }edge[N]; 10 int head[N],num_edge; 11 int time; 12 int dfn[N]; 13 int low[N]; 14 int ans1,ans2; 15 int x,y,n,m; 16 int place[N]; 17 bool f[N]; 18 bool k; 19 void add_edge(int from,int to){ 20 edge[++num_edge].next=head[from]; 21 edge[num_edge].to=to; 22 head[from]=num_edge; 23 } 24 void dfs(int x){ 25 k=0; 26 p.push(x); 27 dfn[x]=low[x]=++time; 28 for(int i=head[x];i;i=edge[i].next){ 29 if(f[edge[i].to]) 30 continue; 31 if(dfn[edge[i].to]) 32 low[x]=min(low[x],dfn[edge[i].to]); 33 else{ 34 dfs(edge[i].to); 35 low[x]=min(low[x],low[edge[i].to]); 36 } 37 } 38 if(low[x]==dfn[x]){ 39 ++ans2; 40 while(p.top()!=x){ 41 f[p.top()]=1; 42 printf("%d ",p.top()); 43 place[p.top()]=ans2; 44 p.pop(); 45 k=1; 46 } 47 f[p.top()]=1; 48 place[p.top()]=ans2; 49 p.pop(); 50 printf("%d ",x); 51 if(k)++ans1; 52 } 53 } 54 int main(){ 55 scanf("%d%d",&n,&m); 56 for(int i=1;i<=n;i++) 57 f[i]=0; 58 for(int i=1;i<=m;i++){ 59 scanf("%d%d",&x,&y); 60 add_edge(x,y); 61 } 62 for(int i=1;i<=n;i++) 63 if(dfn[i]==0){ 64 time=0; 65 dfs(i); 66 } 67 printf("%d ",ans1); 68 printf("%d ",ans2); 69 for(int i=1;i<=n;++i) 70 printf("%d ",place[i]); 71 return 0; 72 }