# DFS — Depth-First Search

> **Inherits from: the stack.** Data structure: graph + stack (প্রায়ই call stack-টাই)। Thinking tweak: একটা path-এ commit করো, যতটা পারো গভীরে যাও, আটকে গেলেই কেবল ফিরে এসো — সুতোর বল নিয়ে গুহা explore করার মতো।

---

## Inheritance-টা, খুলে বলা

DFS হলো stack-এর traversal, ঠিক যেভাবে BFS হলো queue-র:

```text
DFS = a stack + a visited set + "neighbors pile on TOP"
```

Stack last-in-first-out বলে, সবচেয়ে সম্প্রতি discover হওয়া node-টাই পরে explore হয় — তাই search টা siblings try করার আগে এক path ধরে নিচে ঝাঁপ দেয়। BFS-এ একটা শব্দ বদলাও — `popleft` → `pop` — আর তোমার হাতে iterative DFS। ওই একটা শব্দই personality-টা পুরো বদলে দেয়।

## Recursion = একটা implicit stack

বিখ্যাত তিন-লাইনের DFS:

```python
def dfs(node, adj, visited):
    visited.add(node)
    for nxt in adj[node]:
        if nxt not in visited:
            dfs(nxt, adj, visited)
```

কোনো দৃশ্যমান stack নেই — কারণ **Python-এর call stack-টাই stack**। প্রতিটা recursive call একটা frame push করে ("আমি node X-এ আছি, তার neighbor list-এর মাঝপথে"); প্রতিটা return একটা pop করে। [visual-explanation.md](visual-explanation.md) Part 2-এর frame-by-frame trace-এ এই stack-টাকেই `A B D F E C` পর্যন্ত বাড়তে আর গুটিয়ে যেতে দেখেছ।

Iterative জমজটা, যখন recursion depth একটা risk (Python-এর default limit ~1000 frames, আর 10^5 nodes-এর একটা path graph সেটা গুঁড়িয়ে দেবে):

```python
def dfs_iter(start, adj):
    visited = {start}
    stack = [start]
    while stack:
        node = stack.pop()              # LIFO -> deep-first
        for nxt in adj[node]:
            if nxt not in visited:
                visited.add(nxt)
                stack.append(nxt)
    return visited
```

একই visited set, একই O(V + E) cost, siblings-দের মধ্যে visiting order সামান্য আলাদা (explicit stack তাদের list-এর উল্টো order-এ try করে) — যা reachability, components, বা cycle detection-এর correctness-এ কখনোই matter করে না।

## Connected components: DFS-এর signature move

"কতগুলো আলাদা islands / friend groups / networks?" — এখনো visit না হওয়া প্রতিটা node থেকে DFS চালাও; প্রতিটা launch ঠিক একটা গোটা component দখল করে।

```python
def count_components(nodes, adj):
    visited = set()

    def dfs(node):
        visited.add(node)
        for nxt in adj[node]:
            if nxt not in visited:
                dfs(nxt)

    count = 0
    for node in nodes:
        if node not in visited:     # an unclaimed island!
            dfs(node)               # claim ALL of it
            count += 1
    return count
```

Mental model: একটা paint bucket। প্রতিটা top-level `dfs(node)` call এক রঙের রং ঢেলে দেয় যেটা connected সবকিছুতে ছড়িয়ে যায়; answer হলো কয়টা রঙ লাগল। ([Number of Islands](https://leetcode.com/problems/number-of-islands/) হলো এটাই, grid cells-কে nodes ধরে; [Number of Provinces](https://leetcode.com/problems/number-of-provinces/) হলো এটাই, adjacency matrix দিয়ে; [CSES Building Roads](https://cses.fi/problemset/task/1666) চায় components minus one।)

## তিন রঙ দিয়ে cycle detection (directed graphs)

**Directed** graph-এ "already visited" দিয়ে cycle ঘোষণা করা যায় না — হতে পারে তুমি শুধু পুরোনো, শেষ-হয়ে-যাওয়া কোনো region-এ আবার পৌঁছেছ। সমাধান হলো node প্রতি তিনটা state:

```text
WHITE = never touched
GRAY  = currently on the recursion stack (we are INSIDE its exploration)
BLACK = fully finished (we have left it for good)
```

নিয়মটা: **একটা GRAY node-এর সাথে দেখা হওয়া মানেই cycle।** তুমি সামনে হেঁটে নিজেরই অসমাপ্ত পথের দাগে ধাক্কা খেয়েছ — current path-এর ভেতরে একটা loop। BLACK node-এর সাথে দেখা হওয়া নিরীহ: সেই রাস্তা পুরো explore হয়ে গেছে আর কোনো circular কিছুতে যায়নি।

```python
WHITE, GRAY, BLACK = 0, 1, 2

def has_cycle(nodes, adj):
    color = {node: WHITE for node in nodes}

    def dfs(node):
        color[node] = GRAY                  # entering: on the current path
        for nxt in adj[node]:
            if color[nxt] == GRAY:          # ran into our own trail
                return True
            if color[nxt] == WHITE and dfs(nxt):
                return True
        color[node] = BLACK                 # leaving: fully explored
        return False

    return any(color[n] == WHITE and dfs(n) for n in nodes)
```

ঠিক এভাবেই [Course Schedule](https://leetcode.com/problems/course-schedule/) "impossible" ঠিক করে: prerequisites-এর একটা cycle মানে কোনো valid study order নেই (আরও আছে [topological-sort.md](topological-sort.md)-এ)।

**Undirected** graph-এর জন্য test টা সহজ: DFS করতে করতে এমন কোনো visited neighbor দেখা *যে সেই node না, যেখান থেকে এইমাত্র এলে* — মানেই cycle। (অথবা DFS পুরোপুরি বাদ দিয়ে DSU ব্যবহার করো — [../10-disjoint-set-union/](../10-disjoint-set-union/README.md)।)

## Pre-order আর post-order: এক ঝলক, যেটা পরে কাজে দেবে

DFS-এ প্রতিটা node-এর দুটো timestamp থাকে:

- **Pre-order (entry)**: DFS প্রথম যে মুহূর্তে পৌঁছায় — neighbors explore করার আগে।
- **Post-order (exit)**: DFS যে মুহূর্তে ছেড়ে যায় — ALL neighbors পুরোপুরি explore হওয়ার পরে।

```python
def dfs_orders(node, adj, visited, pre, post):
    visited.add(node)
    pre.append(node)                    # entering
    for nxt in adj[node]:
        if nxt not in visited:
            dfs_orders(nxt, adj, visited, pre, post)
    post.append(node)                   # leaving — everything below is done
```

কেন এটা পাত্তা দেবে? **Post-order মানে "আমার সব dependents শেষ হয়ে গেছে।"** একটা DAG-এর post-order উল্টে দাও, পেয়ে যাবে একটা valid topological order ([topological-sort.md](topological-sort.md))। এই timestamp গুলোই পরে competitive programming-এ strongly connected components আর bridge-finding চালায় — DFS-এর exit times এই পুরো repo-র অন্যতম নীরব-শক্তিশালী idea।

(এগুলো [../07-trees/](../07-trees/README.md)-এর tree traversals-এরই generalization: ওখানকার preorder আর postorder ছিল cycle-free graph-এ DFS-এর order।)

## Flood fill: pixels-এ DFS

Image editor-এর paint-bucket tool টা আক্ষরিক অর্থেই DFS: একটা pixel থেকে শুরু করে তাকে recolor করো আর একই-রঙা neighbors-এ recurse করো।

```python
def flood_fill(grid, r, c, new_color):
    R, C = len(grid), len(grid[0])
    old = grid[r][c]
    if old == new_color:                # crucial: avoid infinite re-painting
        return grid

    def dfs(r, c):
        if 0 <= r < R and 0 <= c < C and grid[r][c] == old:
            grid[r][c] = new_color      # painting IS the visited-marking
            for dr, dc in ((-1,0), (1,0), (0,-1), (0,1)):
                dfs(r + dr, c + dc)

    dfs(r, c)
    return grid
```

Elegance-টা খেয়াল করো: আলাদা কোনো visited set নেই — cell recolor করাটাই *হলো* mark। ([Flood Fill](https://leetcode.com/problems/flood-fill/) হুবহু এটাই; Number of Islands হলো flood fill plus একটা counter; [Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/) হলো ocean দুটো থেকে *উল্টোদিকে* চালানো দুটো flood fill।)

## DFS vs BFS, এক নিঃশ্বাসে decision

DFS যখন প্রশ্নটা **structure** নিয়ে — components, cycles, orderings, "explore everything", backtracking-ধাঁচের searches। BFS যখন প্রশ্নটা **distance** নিয়ে। যেকোনোটা যখন নিছক reachability। (পুরো table [bfs.md](bfs.md)-এ।)

DFS-specific সাবধানতা:

- Recursion depth: একটা লম্বা path graph Python-এর stack overflow করায় — iterative-এ যাও, বা সাবধানে limit বাড়াও (`sys.setrecursionlimit`), জেনে রেখো এটা একটা band-aid।
- DFS খুঁজে পায় *একটা* path, *shortest* path না। "minimum steps"-এর জন্য DFS ব্যবহার করা হলো classic wrong-tool error।
- Flood fill-এ নিশ্চিত করো recoloring (বা visited-marking) recurse করার আগে হচ্ছে, নইলে identical-color region চিরকাল loop করে।

## DFS-এর trigger words

"Connected components", "islands/regions/provinces", "detect a cycle", "is it possible to finish" (directed deps), "explore all", "flood fill", "all paths from A to B" (DFS + backtracking — দেখো [../06-recursion-and-backtracking/](../06-recursion-and-backtracking/README.md)), "valid ordering" (DFS post-order route)।

## Representative problems

- [Number of Islands](https://leetcode.com/problems/number-of-islands/) — grid-এ flood fill দিয়ে components।
- [Clone Graph](https://leetcode.com/problems/clone-graph/) — DFS করতে করতে hash map-এ copies বানানো (inherits [../05-hashing/](../05-hashing/README.md))।
- [Course Schedule](https://leetcode.com/problems/course-schedule/) — prerequisite digraph-এ GRAY/BLACK cycle detection।
- [Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/) — দুই border থেকে reverse flood fill, তারপর reaches-এর intersection।
- [CSES Building Teams](https://cses.fi/problemset/task/1668) — DFS (বা BFS) two-coloring; এক রঙের ভেতরে একটা edge মানেই impossible।

Reference treatment: [cp-algorithms DFS](https://cp-algorithms.com/graph/depth-first-search.html)। পরে: [topological-sort.md](topological-sort.md), যেখানে DFS post-order তার প্রথম বড় payoff পায়।