Bog‘langan komponentlarni topish

Shart

$n$ ta cho‘qqi va $m$ ta qirrali yo‘naltirilmagan graf $G$ berilgan. Undagi barcha bog‘langan komponentalarni topish talab qilinadi — cho‘qqilar guruhlari shundayki, guruh ichida har bir cho‘qqidan istalgan boshqasiga yetib borish mumkin, turli guruhlar orasida esa yo‘l mavjud emas.

Yechim

Bu masalani yechish uchun DFS yoki BFS dan foydalanish mumkin.

Aslida biz DFS/BFS ni bir necha marta ishga tushiramiz:

birinchi ishga tushirish birinchi cho‘qqidan boshlanadi va birinchi bog‘langan komponentaning barcha cho‘qqilarini topadi;
so‘ng hali tashrif buyurilmagan birinchi cho‘qqini olamiz va undan aylanib chiqishni boshlaymiz — shunday qilib ikkinchi komponentani topamiz;
va hokazo, barcha cho‘qqilar tashrif buyurilgunga qadar.

Algoritmning umumiy ishlash vaqti: $O(n + m)$ .