1、简介：
在阅读下列内容之前，请务必了解 图论相关概念 中的基础部分。
强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。
强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。
这里要介绍的是如何来求强连通分量。
2、引入：
在介绍该算法之前，先来了解 DFS 生成树，我们以下面的有向图为例：
3、算法思想：
求强连通分量就相当于求环(或类似于环可以一遍又一遍无限走下去，切走不出这个环)的个数。
其他人博客上说什么：树边（tree edge），横叉边（cross edge），反祖边（back edge），前向边（forward edge），这些太复杂了，对像我一样的蒟蒻不友好以下是一段简洁的解释。
先说算法步骤：
1、我们要对一张图(有向图)进行遍历。
记录：dfn[x]: 存x点的时间戳（是第几个遍历这个点的），（相当于记录了遍历的顺序）；
low[x]: 存x点最早能访问到的时间戳。
2、思考：若dfn[x]=low[x]，就说明x点无论怎么走，都无法到达时间戳更靠前的点，证明x点是一个环的开始（环顶）。
3、将遍历到的点依次入栈，当判断到环顶时，栈中的点就是一个强连通分量。
4、详细步骤：
按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的 dfn 与 low 变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点 
和与其相邻的结点 （ 不是 的父节点）考虑 3 种情况：
v未被访问：继续对 v 进行深度搜索。在回溯过程中，用 low[v] 更新 。因为存在从 u 到 v 的直接路径，所以说 v 能够回溯到的已经在栈中的结点，u 也一定能够回溯到。 v被访问过，已经在栈中：根据 low 值的定义，用 dfn[v] 或low[v] 更新 low[u] 。 v被访问过，已不在栈中：说明v已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。
5、例题：（洛谷 P2863 [USACO06JAN] The Cow Prom S）
//洛谷 P2863 [USACO06JAN] The Cow Prom S #include<bits/stdc++.h> using namespace std; const int N=2e4+2,M=5e4+2; int n,m,dfn[N],low[N],first[N],stk[N],siz[N],top=0,tot=0,cnt=0,ans=0; bool in[N]; struct node{int v,ne;}e[M]; void add(int u,int v){ e[++tot]={v,first[u]}; first[u]=tot; } void tarjan(int u){ //tarjan算法求强连通分量 dfn[u]=low[u]=++tot; in[u]=1; //表示u点在栈中 stk[++top]=u; //将u记入栈中 for(int i=first[u];i;i=e[i].ne){ int v=e[i].v; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); //更新low[u]值的意义是让u点不提前出栈 } else if(in[v]) low[u]=min(low[u],low[v]); } if(low[u]==dfn[u]){ int y; ++cnt; do{ y=stk[top--];in[y]=0; siz[cnt]++; }while(u!=y); } } int main(){ scanf("%d%d",&n,&m); int u,v; for(int i=1;i<=m;++i){ scanf("%d%d",&u,&v); add(u,v); //建单向边 } for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i); //图有可能不连通，存在几个分开的图 for(int i=1;i<=cnt;++i) if(siz[i]>1) ans++; //siz[]记录每一个强连通分量的大小 printf("%d",ans); return 0; }
6、后继知识
学了tarjan强连通分量，就可以学习缩点等，真正涉及到应用的东西。