給定圖G=

若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是強連通圖。

透過以上定義我們容易知道:

有向圖的強連通圖一定是迴路，否則不可互達。

無向圖的連通圖不是迴路，但是有迴路的無向圖一定是連通的。

連通分量是指無向圖中的極大連通子圖。有向圖中的極大強連通子圖稱做有向圖的強連通分量。

所以只需對所給出的圖做分解就可得出。