强连通图（Strongly Connected Graph）是指在
有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在
路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的
强连通分量。
定理及其证明
定理：一个
有向图是
强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。
证明：
（1）充分性：如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。
（2）必要性：如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾。
强连通图的边问题
有n个顶点的强连通图最多有n（n-1）条边，最少有n条边。
（1）最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-1）/2条边，而由于强连通图是有向图，故每条边有两个方向，n（n-1）/2×2=n（n-1），故有n个顶点的强连通图最多有n（n-1）条边。
（2）最少的情况：即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。
下面举例说明：如图1所示，设ABCD四个点构成强连通图，则：
（1）边数最多有4×3=12条，如图1所示。
（2）边数最少有4条，如图2所示。
强连通图的判断
问题：给一个有向图，判断给图是否是强连通的。
如图3所示，则是一个强连通图。
对于无向图则比较简单，只需要从某一个顶点出发，使用
BFS或
DFS搜索，如果可以遍历到所有的顶点，则给定的图是连通的。
但这种方法对有向图并不适用，例如 ： 1 -> 2 -> 3 -> 4，并不是强连通图。
方法一
可以调用DFS搜索 V 次，V是顶点的个数，就是对每个顶点都做一次DFS搜索，判断是否可达。这样的复杂度为O(V*(V+E))。
方法二
可以参考求解连通分量的算法Tarjan算法，我们可以在O(V+E) 的时间内找到所有的连通分量，如果连通分量的个数为1，则说明该图是强连通的。