10.5. Erősen összefüggő komponensek

Egy G irányított gráf erősen összefüggő komponense a csúcsok egy maximális U halmaza, melynek bármely két u és v csúcsára teljesül a következő: u-ból vezet út v-be és v-ből vezet út u-ba. A gráfot erősen összefüggő komponenseire bontó algoritmus felhasználja a G gráf GT transzponáltját. A GT -nek akkor és csak akkor éle az (u, v), ha G-nek éle (v, u). Az összefüggő komponenseket a csúcsok és élek számának összegével arányos bonyolultságú algoritmussal meghatározhatjuk. A megadott algoritmus tetszőleges végrehajtásával meghatározhatjuk az összefüggő komponenseket.

Function ERőSEN-ÖSSZEFÜGGő-KOMPONENSEK(G) 
Input: G gráf Eredmény: a gráf alapján felépít egy erdőt, ahol egy fa felel meg egy komponensnek 
1 MÉLYSÉGI-KERESÉS(G) meghívása, az u.ki értékek meghatározása. 
2 GT , a G gráf transzponáltjának meghatározása 
3 MÉLYSÉGI-KERESÉS(GT ) meghívása, ám a for ciklusban a pontokat u.ki szerinti csökkenő sorrendben kell végigjárni. 
4 Az így kapott mélységi fák csúcsai alkotnak egy-egy összefüggő komponenst.