ps：本人太菜了，强连通分量是最近才开始上手写题的，勿喷。
part1：判断图是否联通
相信不用多说：dfs一遍或者并查集
如果你是普及选手：
dfs做法：
从任意一个点开始遍历整个图，如果所有点都被遍历一遍，就是联通的。
并查集：
把每个边的两个点并在一起，看看是否所有点被并到一个集合里了。
计算连通块也可以用以上方法解决。
part2：强连通分量
①：
什么是强连通分量？
“有向图强连通分量：在有向图G中，如果两个顶点 \(v_i\),\(v_j\) 间（\(v_i\) \(\neq\) \(v_j\)）有一条从 \(v_i\) 到 \(v_j\) 的有向路径，同时还有一条从 \(v_j\) 到 \(v_i\) 的有向路径，则称两个顶点强连通 \((strongly\) \(connected)\)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量 \((strongly\) \(connected\) \(components)\)。”
说的通俗易懂一些：
一张有向图，其中有一个子图，这个子图需要满足：图中任意两点 \(v_i\), \(v_j\) (\(v_i\neq v_j\))，有一条路径可以从 \(v_i→v_j\)，还有一条路径可以从 \(v_i←v_j\)。
强连通分量就是这张图中满足需求且最大的子图。
②：
如何求取强连通分量？
DFS
可能会出现以下四种边：
1.树边：DFS森林中某棵树上的边。
2.后向边：由森林中某棵树上的一个结点指向其祖先结点的点（又被称为返祖边）。
3.前向边：由森林中某棵树上的一个结点指向其后代结点的边（一般来讲删除这种边以后并不会影响结果）。
4.交叉边：是在两个不构成“祖先—后代”关系的结点之间的边（又称横插边）。
接下来引入两个数组：
\(dfn\) 数组以及 \(low\) 数组
\(dfn\) 就是 \(dfs\) 序，\(dfn[i]\) 记录的是顶点 \(i\) 第几个被遍历。
\(low\) 数组表示的是每个点能回到的 \(dfn\) 序最小的结点是哪个。
\(dfn\) 和 \(low\) 数组需要用 \(dfs\) 来求取.
在计算 \(dfn\) 和 \(low\) 的同时，我们也要用栈来存储遍历的点，当某个点 \(dfn[x]==low[x]\) 时，把从这个点到栈顶的点全部取出，这就是一个强连通分量
这就是tarjan算法
代码：
const int maxn=1e4+10;
vector<int> edge[maxn];
int dfn[maxn],low[maxn];
int cnt;
int s[maxn],top;
bool instack[maxn];
int ans,scc[maxn];
void tarjan(int u)
{
s[++top]=u;//把这个点扔进栈
instack[u]=1;
dfn[u] =low[u] =++cnt;
for(int i=0;i<edge[u].size();i++)
{
int v=edge[u][i];
if(!dfn[v])
{ //如果下一个点没有被搜过，
tarjan(v);//继续搜
low[u]=min(low[u],low[v]);//更新low
}
else if(instack[v])
{ //如果下一个点已经被搜过，看他在不在栈里
low[u]=min(low[u],dfn[v]);//更新low
}
}
if(dfn[u]==low[u])
{
ans++;//答案++，第几个强连通分量
int v;
while(1)
{
v=s[top--];
scc[v]=ans; //打标记
instack[v]=0;//出栈
if(v==u)
break;
}
}
}
part3：tarjan的其他应用
1.求割边割点
割边定义：在无向连通图 ，若删除边 \(u->v\) 后，原图变成了两个联通分量，则称这条边是⼀条割边
割点定义：在无向连通图 上，若删除节点 \(u\) 和所有与其相连的边的集合 之后，原图变成了两个以上的连通分量，则称节点 \(u\) 是⼀个割点。
2.缩点
将一整个联通分量缩成一个点之后跑拓扑排序
3.点双/边双连通分量
原文地址：http://www.cnblogs.com/Y2y7m/p/16874969.html
