Motivace: Máme ohromné bludiště, které vzniklo tak, že někdo v ohromné hale postavil z cihel spoustu zdí. Do haly vede několik vchodových dveří. Chtěli bychom zjistit, kolik oddělených bludišť v hale je (několik vchodů může vést do stejného bludiště). Dále chceme zjistit, kolik nejméně zdí musíme probourat, abychom dostali jedno velké bludiště.

Definice: Graf je souvislý, pokud mezi každýma dvěma vrcholy vede cesta. Pokud graf není souvislý, tak se skládá z jednotlivých částí, které už souvislé jsou. Těmto částem budeme říkat komponenty souvislosti. Jinak řečeno, komponenta souvislosti je maximální souvislý podgraf.

Pro nalezení komponent souvislosti použijeme průchod do hloubky s malou úpravou. Víme, že procedura Projdi($v$) projde všechny vrcholy dosažitelné z $v$ tj. vrcholy komponenty obsahující vrchol $v$. Proto stačí, když si při tomto průchodu budeme vrcholy označovat číslem komponenty.

Časová složitost nalezení komponent souvislosti stejná jako časová složitost DFS a to je $\OO(n+m)$.