DFS applications — cycle detection (directed and undirected)

3.5.6 · Coding › Graphs

DO ALAG rules KYU?

Colors kyun matter karte hain (directed): Ek directed graph mein, kisi black node tak dobara pahunchna theek hai — iska sirf matlab hai ki do paths merge ho rahi hain (ek cross/forward edge), koi cycle nahi. Lekin kisi gray node tak pahunchna matlab hai ki tumne ek aisi path dhundh li jo ek aise ancestor ke paas loop back karti hai jiske andar tum abhi bhi ho → cycle.

Parent-exception kyun (undirected): Har undirected edge $u - v$ dono taraf store hoti hai. Jab tum $u \to v$ jaate ho, tab $v$ se tum $u$ ki taraf wapas jaane wali edge dekhoge jo already visited hai. Yeh cycle NAHI hai — yeh wahi edge hai. Isliye tumhe immediate parent ko ignore karna padta hai. Lekin koi bhi doosra already-visited node dekhna ek genuine doosri path back ko indicate karta hai → cycle.

Figure — DFS applications — cycle detection (directed and undirected)

KAISE: Directed cycle detection (3-color DFS)

Formula Directed algorithm (states se derived)

color[] ko saara White maintain karo. Har White node ke liye, dfs run karo.

dfs(u):
    color[u] = GRAY
    for v in adj[u]:
        if color[v] == GRAY:   return True   # back edge → cycle
        if color[v] == WHITE and dfs(v): return True
    color[u] = BLACK
    return False

GRAY check pehle kyun? Jo neighbor gray hai woh current stack par baitha hai → usse edge ek loop close karti hai. BLACK kyun allow karte hain? Black matlab doosri branch par finish — koi live loop nahi.

KAISE: Undirected cycle detection

Formula Undirected algorithm (derived)

visited[] maintain karo. dfs(u, parent) run karo:

dfs(u, parent):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            if dfs(v, u): return True
        elif v != parent:        # visited AUR woh edge nahi jisse hum aaye
            return True          # cycle!
    return False

v != parent kyun? Edge $p a r e n t - u$ ki reverse copy dikhai degi; use ignore karna ek false alarm rokta hai. Koi bhi doosra visited neighbor = doosra raasta = real cycle.

Common mistake Classic errors ko steel-man karna

Galti 1 — directed graphs par parent-trick use karna. Yeh sahi lagta hai ("jahan se aaya wahan se ignore karo"). Kyun fail hoti hai: directed edges symmetric nahi hoti; ignore karne ke liye koi spurious reverse edge nahi hai, aur ek sacchi 2-cycle $A \to B \to A$ galat tarike se skip ho jaayegi. Fix: 3 colors use karo, GRAY check karo.

Galti 2 — undirected par GRAY/colors logic use karna aur parent bhool jaana. Tum HAR edge par immediate-parent reverse edge ko cycle flag kar doge. Kyun tempting lagta hai: "visited node reach hona = cycle" universal lagta hai. Fix: v != parent add karo.

Galti 3 — undirected mein parallel edges / self-loops. $u, v$ ke beech do edges hone par, v != parent test cycle miss kar sakta hai. Fix: sirf parent nahi, edge-index visited track karo jab multigraphs allowed hoon. Ek self-loop $u - u$ khud hi ek cycle hai.

Galti 4 — SAARE components par iterate na karna. Ek cycle ek disconnected component mein chupi ho sakti hai. Fix: for u: if not visited[u]: dfs(u) loop karo.

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho tum ek maze mein chal rahe ho aur peeche string khol rahe ho. Directed maze (one-way doors): agar ek darwaza tumhe ek aisi jagah le jaata hai jahan tumhari string abhi bhi zameen par padi hai saamne (tumne use abhi pack nahi kiya), tum ek chakkar mein gaye ho. Agar string wahan pehle se roll back ho chuki hai (tumne woh area finish kar liya), toh theek hai. Undirected maze (normal doors): har darwaze se guzarte waqt, peeche wala darwaza wahi hai jahan se tum aaye — use ignore karo! Lekin agar tum kisi aise room tak pahuncho jahan tum pehle se ja chuke ho ek alag darwaze se, toh maze mein ek loop hai.

Complexity

Flashcards

Directed graph: cycle tab exist karti hai jab DFS kaunsi tarah ki edge dhundhe?

Ek back edge — ek aise node tak edge jo currently GRAY hai (recursion stack par).

Teen DFS colors WHITE/GRAY/BLACK ka kya matlab hai?

White = unvisited; Gray = visited lekin abhi bhi recursion stack par; Black = poori tarah finished/popped.

Directed graph mein kisi BLACK node tak pahunchna cycle indicate kyun nahi karta?

Black matlab us node ka DFS doosri branch par pehle hi finish ho chuka hai; woh edge ek cross/forward edge hai, live stack par loop back nahi.

Undirected cycle detection: DFS ke dauran cycle ki condition kya hai?

Ek already-visited node tak edge jo immediate parent NAHI hai.

Undirected DFS mein v != parent check kyun?

Har undirected edge dono directions mein store hoti hai; jis edge se hum aaye uski reverse copy falsely cycle jaisi dikhegi, isliye hum parent ko exclude karte hain.

Directed graphs ke liye parent-trick kyun use nahi kar sakte?

Directed edges symmetric nahi hoti, isliye koi spurious reverse edge nahi hai; parent-trick ek sacchi 2-cycle A→B→A bhi miss kar degi.

DFS cycle detection ki time complexity?

O(V + E), space O(V).

n nodes wale tree mein kitni edges hoti hain, aur ek extra edge kya karti hai?

n−1 edges; koi bhi additional edge exactly ek cycle create karti hai.

Disconnected graphs mein cycles detect karna kaise ensure karte hain?

Saare vertices par loop karo aur kisi bhi unvisited node se DFS shuru karo.

Sabse chhoti directed cycle aur sabse chhoti undirected cycle (simple)?

Directed: 2 nodes (A→B→A) ya self-loop; Undirected (simple): 3 nodes (triangle).

Connections

Depth-First Search — woh traversal engine jis par yeh rely karte hain.
Topological Sort — tabhi possible hai jab directed graph acyclic ho (DAG); same back-edge test.
Union-Find (DSU) — DFS ke bina alternative undirected cycle detection.
Back Edges and Edge Classification — tree/back/forward/cross edges.
Strongly Connected Components — DFS finish times par built.
Bipartite Checking — ek aur DFS/BFS coloring application.