Lesson 6 � Advanced

Top Graph Problems (LeetCode)

Graphs se LeetCode par bahut problems aati hain. Is lesson mein top 10 problems ke patterns dekhenge � BFS, DFS, Union-Find, Topological Sort kahan use hota hai.

Problem Patterns

Graph problems ko 4 main patterns mein divide kar sakte ho:

• BFS Pattern: Shortest path in unweighted graph, level-order traversal, minimum steps.
• DFS Pattern: Connected components, path finding, backtracking, island counting.
• Union-Find Pattern: Dynamic connectivity, cycle detection in undirected graph, merging components.
• Topological Sort Pattern: Ordering with dependencies, cycle detection in directed graph.

Top 10 Problems

1. Number of Islands (LC 200) � DFS/BFS

2D grid mein '1' (land) aur '0' (water) hai. Kitne islands hain✓ Har connected '1' ka group ek island hai.

def num_islands(grid):
 if not grid: return 0
 count = 0
 for i in range(len(grid)):
 for j in range(len(grid[0])):
 if grid[i][j] == '1':
 dfs(grid, i, j)
 count += 1
 return count

def dfs(grid, i, j):
 if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
 return
 grid[i][j] = '0' # visited mark karo
 dfs(grid, i+1, j)
 dfs(grid, i-1, j)
 dfs(grid, i, j+1)
 dfs(grid, i, j-1)

2. Clone Graph (LC 133) � DFS/BFS + HashMap

Ek graph ka deep copy banao. Har node ka clone banao aur neighbors ko map karo.

3. Course Schedule (LC 207) � Topological Sort / Cycle Detection

Kya sab courses complete kar sakte ho prerequisites ke according✓ Yeh cycle detection hai directed graph mein.

4. Course Schedule II (LC 210) � Topological Sort

Valid course order return karo. Kahn's algorithm use karo.

5. Alien Dictionary (LC 269) � Topological Sort

Words ke order se alien language ka character order nikalo. Prefix se dependency nikalte hain.

6. Word Ladder (LC 127) � BFS

Begin word se end word tak transformation karo � har step mein sirf ek letter change karo aur dictionary mein hona chahiye. BFS shortest path dhoondta hai.

7. Pacific Atlantic Water Flow (LC 417) � DFS/BFS

Grid mein water flow karta hai. Wo cells nikalo jo Pacific aur Atlantic dono oceans tak flow kar sakte hain.

8. Redundant Connection (LC 684) � Union-Find

Ek extra edge hai jo cycle bana raha hai. Woh edge nikalo. Union-Find mein jab dono nodes ka same parent ho toh woh edge redundant hai.

9. Accounts Merge (LC 721) � Union-Find

Same person ke alag-alag accounts merge karo based on common email. Union-Find se connected components nikalo.

10. Is Graph Bipartite (LC 785) � BFS/DFS Coloring

Graph ko 2 colors se color kar sakte ho bina adjacent nodes ke same color ho✓ BFS/DFS se color karo � har neighbor ka color alag rakho.

Try it: code khud likho

Problem Solving Tips

• Pehle identify karo ki graph directed hai ya undirected, weighted hai ya nahi.
• Shortest path chahiye BFS (unweighted) ya Dijkstra (weighted).
• Connected components nikalne hain toh DFS/BFS.
• Ordering chahiye toh Topological Sort.
• Dynamic connectivity / merging toh Union-Find.
• Grid problems mein har cell ko node samjho, 4 directions se edges hain.

Common mistakes

• Grid problems mein boundary check karna bhool jaana � index out of range error.
• Visited set mein add karna bhool jaana � infinite loop mein phas jaoge.
• Union-Find mein path compression lagana bhool jaana � time complexity O(n) ho jayegi O(a(n)) ki jagah.
• Directed graph mein undirected samajh kar edges dono taraf add karna � galat answer aayega.
• DFS recursion limit mein phas jaana � Python mein recursion limit check karo ya iterative DFS use karo.