一、强连通分量
在有向图G中，如果任意两个不同的顶点相互可达，则该有向图为强连通的；一个有向图G的极大连通子图称为G的强连通分支；将有向图G的每一条边反向形成的图称为G的转置 Gt.
1.1 有向图的一些定理
-
有向无环图中唯一出度为0的点，一定可以由任何点出发到达
图中节点的数目为有限多个，而且无环，因此从任何点出发往前走，一定终止于出度为0的点，否则走N+1步（N为图中节点的数目），则必然有一个点被走了两次，形成了环，与无环矛盾！ -
有向无环图中所有入度不为0的点，一定可以由某个入度为0的点出发可达
由于无环，所以从任何入度不为0的点往回走，必然终止于一个入度为0的点。
1.2 强连通分量的求解
一个有向图G可以存在多个极大连通子图，即多个强连通分支。求一个有向图的强连通分支的方法主要有：Korasaju算法和Tarjan算法。
1.2.1 Korasaju算法
1. 深度优先遍历图G，算法每个节点u的结束时间f[u],起点如何选择无所谓；
2. 深度优先遍历G的转置图Gt，选择遍历的起点的时候，按照节点的结束时间从大到小进行。遍历的过程中，一边遍历，一边给节点做分类标记，每找到一个新起点，分类标记就加1；
3. 第2步中产生的标记值相同的节点构成深度优先森林中的一棵树，也即一个强连通分量
1.2.2 Tarjan算法
1. 做一遍DFS，用dfn[i]表示编号为i的节点在DFS过程中的访问序号（也可以叫做开始时间）。DFS过程中会形成一棵搜索树，在搜索树上越先遍历到的节点，dfn的值就越小。dfn值越小的节点，就称为越“早”。
2. low[i]表示从i节点出发DFS过程中i下方节点（开始时间大于dfn[i]，且由i可达的节点）所能到达的最早的节点的开始时间。初始时 low[i] = dfn[i].
3. DFS过程中，碰到哪个节点，就将哪个节点入栈。栈中节点只有在其所属的强连通分量已经全部求出时，才会出栈。
4. 如果发现某节点u有边连接到栈里的节点v，则更新u的low值为 min(low[u], dfn[v])。若low[u]被更新为dfn[v]，则表明目前发现u可达的最早的节点是v。
（1）对于u的子节点v，从v出发进行的DFS结束回到u时，使得low[u] = min(low[u], low[v])。因为u可达v，所以v可达的最早的节点，也是u可达的。
（2）如果一个节点u，从其出发进行的DFS已经全部完成并回到u，而且此时 low[u] == dfn[u]，说明u可达的所有节点，都不能到达任何比u早的节点——那么，该节点u就是一个强连通分量在DFS搜索树中的根。此时，显然栈中u上方的节点，都是不能到达比u早的节点的。将栈中节点弹出，一直弹到u（包括u），弹出的节点就构成了一个强连通分量。
void Tarjan(int u){
dfn[u] = low[u] = ++index;
stack.push(u);
for each(u,v) in E{
if (v is not visited){
Tarjan(v);
low[u] = min(low[u], low[v]);
}else if (v in stack){
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]){ //u是一个强连通分量的根
repeat
v = stack.pop
print v
until (u == v)
}//退栈，把整个强连通分量都弹出来
}
二、割点和桥
无向连通图中，如果删除某点后，图变成不连通，则称该点为割点
无向连通图中，如果删除某边后，图变成不连通，则称该边为桥
求割点和桥的Tarjan算法
思路和求有向图的强连通分量类似，在深度优先遍历整个图过程中形成一棵搜索树。定义dfn[u]为节点u第一次被访问到的时间（序号），low[u]为u或者u的子树中能够通过非父子边（父子边就是搜索树上的边）追溯到的最早的节点的DFS开始时间。
一个顶点u是割点，当且仅当满足（1）或（2）
（1）u为树根，且u有多于一个子树
（2）u不为树根，且存在(u,v)为树枝边（或称父子边，即u为v在搜索树中的父亲），使得 dfn(u) <= low(v)
一条边(u,v)是桥，当且仅当
(u,v)为树枝边，且满足dfn(u) < low(v)。注意，(u,v)不能有重边。
Tarjan算法在DFS过程中判断割点或桥
void Tarjan(u){
dfn[u] = low[u] = ++index;
for each(u,v) in E{
if (v is not visited){
Tarjan(v)
low[u] = min(low[u], low[v])
if(d[u] < low[v])
（u，v）为桥
}else if (v 不是 u的父节点）{
low[u] = min(low[u], dfn[v]);
}
}
if (u 为根）
u是割点 <=> u 有至少两个子节点
else
u是割点 <=> u 有一个子节点v，满足 dfn[u] <= low[v]
}
Tarjan算法之后判断割点或桥
可以先用Tarjan进行dfs算出所有点的low和dfn值，并记录dfs过程中每个点的父节点，然后再把所有点看一遍，看起low和dfn，以找出割点和桥。
找桥的时候，需要注意有无重边，若有重边，则不是桥。
三、无向连通图点双连通分支
无向连通图的点双连通分支是指不包含割点的极大连通子图。
1. 建立一个栈，存储当前双连通分支，搜索图时，每找到一条树枝边或反向边（连到树中祖先的边），就把这条边加入栈中。
2. 如果遇到某树枝边(u,v)满足dfn[u] <= low[v]，说明u是一个割点，此时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。
3. 割点可以属于多个点双连通分支，其余点和每条边只能属于一个点双连通分支
四、无向连通图边连通分支
无向连通图的边双连通分支是指不包含桥的极大连通子图。
求无线连通图的边连通分支，只需要在求出所有的桥以后，把桥边删除，原图就变成了多个连通块，则每个连通块就是一个边连通分支。
桥不属于任何一个边连通分支，其余的边和每个顶点都属于且只属于一个边连通分支。