dfs

DFS (chuqurlik bo‘yicha qidiruv) — bir yo‘ldan oxirigacha boradi, keyin orqaga qaytadi. O(V + E).

import sys
sys.setrecursionlimit(10**6)

seen = [False] * n
def dfs(v):
    seen[v] = True
    for to in g[v]:
        if not seen[to]:
            dfs(to)

components = 0
for v in range(n):
    if not seen[v]:
        components += 1
        dfs(v)

Nimalarni topadi

• Bog‘lanish komponentalari soni (yuqoridagi kod).
• Sikl borligi: yo‘naltirilgan grafda «hozir stekda turgan» uchga qaytish — sikl.
• Topologik tartib: DFS tugagan tartibni teskari aylantiring.
• To‘rdagi «orollar» soni.

Katta grafda rekursiya chuqurligi muammo bo‘lsa, DFS ni oddiy stek bilan yozing.