单向连通图
给定图G=<V,E>.设G中定点和边的交替序列为v0e1e2…el.若T满足如下条件：v(i-1)和vi是ei的端点(G为有向图时要求v(i-1)是ei的始点，vi是ei的终点)，i=1,2…,l,则称T为v0到vl的通路。vo，vl分别称为此通路的起点和终点。T中所含边的数目l称为T的长度。当v0=vl时，称通路为回路。在无向图G中，若顶点vi与vj之间存在通路，则称vi与vj是连通的。规定vi与自身是连通的。设D为一个有向图。如果略去D中各边的方向所得的无向图是连通图，则称D是弱连通图或连通图。若D中任意2顶点至少一个可达另一个，则称D是单向连通图。若D中任意2顶点都是相互可达的，则称D是强连通图。通过以上定义我们容易知道:有向图的强连通图一定是回路，否则不可互达。无向图的连通图不是回路，但是有回路的无向图一定是连通的。连通分量是指无向图中的极大连通子图。有向图中的极大强连通子图称做有向图的强连通分量。所以只需对所给出的图做分解就可得出。