Graphs in Practice: DFS / BFS / Topological Sort / Union-Find via 5 Problems (LC 200/207/133/547/269)

Graph problems look the most intimidating, but they boil down to two steps: ① translate the prompt into "nodes + edges," and ② pick the right tool. There are really just three tools:

• Traversal (DFS / BFS): visiting, connected components, shortest steps.
• Topological sort: dependencies, ordering, cycle detection.
• Union-Find (DSU): dynamic merging, counting components, "same group?"

This post drills all three across 5 problems, continuing the full derivation flow:

📋 Problem → 🧭 break down → brute force → bottleneck → insight → optimum → code

• Grid flood fill (200) → topological sort for cycle detection (207) → cloning a graph with a hash map (133) → Union-Find to count components (547) → character topological ordering (269)

① LC 200 — Number of Islands

📋 Problem: Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is land connected 4-directionally, surrounded by water.

Example: grid = [["1","1","0"],["1","0","0"],["0","0","1"]] → 2

🧭 From reading the problem to the solution

1. Break it down: the grid is an implicit graph — each cell is a node, the four neighbors are edges. "Number of islands" = number of connected components.
2. Brute force: DFS/BFS from each cell, but avoid recounting the same island.
3. Key insight (flood fill): scan each cell; when you hit a '1', increment the count and DFS to "sink" the whole island (mark it '0'), so each island is counted once.
4. Optimum: scan + DFS sink. Mutate the grid itself as the visited marker to save space.

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'                       # sink it (mark visited)
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

void dfs(vector<vector<char>>& grid, int r, int c) {
    int rows = grid.size(), cols = grid[0].size();
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;
    grid[r][c] = '0';                           // sink it
    dfs(grid, r+1, c); dfs(grid, r-1, c);
    dfs(grid, r, c+1); dfs(grid, r, c-1);
}
int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    int count = 0;
    for (int r = 0; r < grid.size(); r++)
        for (int c = 0; c < grid[0].size(); c++)
            if (grid[r][c] == '1') { count++; dfs(grid, r, c); }
    return count;
}

• Complexity: O(m·n) time, O(m·n) space (worst-case recursion; or BFS with a queue).
• Pitfall: ① put bounds checks at the top of DFS to skip pre-call guards; ② sinking (marking visited) is essential, or you recurse forever / double-count; ③ for huge grids recursion may overflow — BFS is safer.

② LC 207 — Course Schedule

📋 Problem: There are numCourses courses (0 to n-1); prerequisites[i] = [a, b] means you must take b before a. Return whether you can finish all courses.

Example: numCourses = 2, prerequisites = [[1,0]] → true; [[1,0],[0,1]] → false (mutual prereq → cycle)

🧭 From reading the problem to the solution

1. Break it down: courses are nodes, "prerequisite" is a directed edge. "Can finish" ⟺ does this directed graph have a cycle (a cycle deadlocks forever).
2. Brute force: DFS from each node to find cycles — easy to get the state-marking wrong.
3. Key insight (topological sort / Kahn's BFS): compute each node's in-degree (how many prereqs point to it). Queue the zero-in-degree nodes (no unmet prereqs), "take" them one by one, decrement the in-degree of what they point to, and enqueue any that hit zero. If you can take all courses → no cycle; getting stuck means a cycle.
4. Optimum: Kahn's algorithm (BFS topological sort), which doubles as a valid order.

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * numCourses
    for course, pre in prerequisites:
        graph[pre].append(course)              # pre → course
        indegree[course] += 1
    q = deque(i for i in range(numCourses) if indegree[i] == 0)
    seen = 0
    while q:
        node = q.popleft()
        seen += 1
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)
    return seen == numCourses                  # all taken → no cycle

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses);
    vector<int> indegree(numCourses, 0);
    for (auto& p : prerequisites) {
        graph[p[1]].push_back(p[0]);           // pre → course
        indegree[p[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < numCourses; i++)
        if (indegree[i] == 0) q.push(i);
    int seen = 0;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        seen++;
        for (int nxt : graph[node])
            if (--indegree[nxt] == 0) q.push(nxt);
    }
    return seen == numCourses;
}

• Complexity: O(V + E) time and space.
• Pitfall: ① get the edge direction right (pre → course); ② cycle test = whether topological sort visited all nodes; ③ to return the order (LC 210), just record node into an array instead of counting.

③ LC 133 — Clone Graph

📋 Problem: Given a node in a connected undirected graph, return a deep copy of the graph. Each node has a val and a list of neighbors.

Example: adjList = [[2,4],[1,3],[2,4],[1,3]] → a brand-new graph with identical structure

🧭 From reading the problem to the solution

1. Break it down: copy the whole graph — the catch is cycles and shared neighbors: mid-copy you hit an already-copied node and must not copy it again.
2. The wrong instinct: plain DFS copy loops forever on a cycle.
3. Key insight (hash map old→new): keep a map "original node → its clone." Before copying a node, check the map: if present, return that clone (this breaks cycles); otherwise create the clone, register it, then recurse into its neighbors.
4. Optimum: DFS + a clones hash map.

def cloneGraph(node):
    if not node:
        return None
    clones = {}
    def dfs(n):
        if n in clones:                        # already cloned → reuse
            return clones[n]
        copy = Node(n.val)
        clones[n] = copy                       # register BEFORE recursing
        for nei in n.neighbors:
            copy.neighbors.append(dfs(nei))
        return copy
    return dfs(node)

Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    unordered_map<Node*, Node*> clones;
    function<Node*(Node*)> dfs = [&](Node* n) -> Node* {
        if (clones.count(n)) return clones[n]; // reuse
        Node* copy = new Node(n->val);
        clones[n] = copy;                      // register before recursing
        for (Node* nei : n->neighbors)
            copy->neighbors.push_back(dfs(nei));
        return copy;
    };
    return dfs(node);
}

• Complexity: O(V + E) time, O(V) space.
• Pitfall: register the clone in the map BEFORE recursing into neighbors — otherwise on a cycle a neighbor recurses back to a not-yet-registered node and loops forever. This is the crux.

④ LC 547 — Number of Provinces

📋 Problem: n cities; isConnected[i][j] = 1 means cities i and j are directly connected. A "province" is a group of directly or indirectly connected cities. Return the number of provinces.

Example: isConnected = [[1,1,0],[1,1,0],[0,0,1]] → 2

🧭 From reading the problem to the solution

1. Break it down: counting connected components again, same essence as the islands problem. DFS works, but the adjacency-matrix form is perfect to showcase Union-Find.
2. Idea: start with each city as its own group (parent = itself). Scan the matrix and union two groups whenever i, j are connected.
3. Key insight (Union-Find): at the end, the number of cities that are still their own root is the number of components (provinces). With path compression, find is nearly O(1).
4. Optimum: DSU over the upper-triangular matrix.

def findCircleNum(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]      # path compression
            x = parent[x]
        return x
    def union(a, b):
        parent[find(a)] = find(b)
    for i in range(n):
        for j in range(i + 1, n):              # upper triangle
            if isConnected[i][j]:
                union(i, j)
    return sum(1 for i in range(n) if find(i) == i)

class DSU {
public:
    vector<int> parent;
    DSU(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;                              // path compression
    }
    void unite(int a, int b) { parent[find(a)] = find(b); }
};
int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    DSU dsu(n);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (isConnected[i][j]) dsu.unite(i, j);
    int count = 0;
    for (int i = 0; i < n; i++) if (dsu.find(i) == i) count++;
    return count;
}

• Complexity: O(n²·α(n)) time (dominated by scanning the matrix), O(n) space.
• Pitfall: ① the matrix is symmetric — scan only the upper triangle to avoid duplicates; ② path compression keeps find amortized near O(1); without it, it degrades; ③ count provinces = count roots (find(i) == i), not the number of unions.

💡 Union-Find signal: "dynamic merging, same-group checks, counting components" with edges given incrementally → reach for DSU; if the graph is given all at once and you must walk paths, DFS/BFS is fine too.

⑤ LC 269 — Alien Dictionary

📋 Problem: An alien language uses lowercase letters in an unknown order. Given words sorted by that language's dictionary rules, derive an order of letters (any valid one); return "" if none exists.

Example: words = ["wrt","wrf","er","ett","rftt"] → "wertf"; words = ["z","x","z"] → "" (contradiction)

🧭 From reading the problem to the solution

1. Break it down: letters are nodes, "letter a before b" is a directed edge — topological sort again, with characters instead of integers as nodes.
2. How to build edges? Compare adjacent words, find the first differing character a, b, yielding an edge a → b (a before b), then stop (later characters tell you nothing).
3. Key insight + two traps: ① an edge comes only from the first differing char; ② prefix contradiction: for ["abc","ab"], a longer word before its own prefix is invalid input — return "". Then topologically sort the character graph; a cycle (contradiction) also returns "".
4. Optimum: build the graph → Kahn's topological sort, checking all characters were visited.

from collections import deque

def alienOrder(words):
    graph = {c: set() for w in words for c in w}
    indegree = {c: 0 for c in graph}
    for first, second in zip(words, words[1:]):
        for a, b in zip(first, second):
            if a != b:                         # first differing char → edge
                if b not in graph[a]:
                    graph[a].add(b)
                    indegree[b] += 1
                break
        else:                                  # no diff in the shared prefix
            if len(second) < len(first):       # prefix violation → invalid
                return ""
    q = deque(c for c in indegree if indegree[c] == 0)
    res = []
    while q:
        c = q.popleft()
        res.append(c)
        for nxt in graph[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)
    return ''.join(res) if len(res) == len(graph) else ""   # cycle → ""

string alienOrder(vector<string>& words) {
    unordered_map<char, unordered_set<char>> graph;
    unordered_map<char, int> indegree;
    for (auto& w : words)
        for (char c : w) { graph[c]; indegree[c]; }   // register all chars
    for (int i = 0; i + 1 < (int)words.size(); i++) {
        string& a = words[i]; string& b = words[i+1];
        int len = min(a.size(), b.size()), j = 0;
        for (; j < len; j++) {
            if (a[j] != b[j]) {                        // first differing char
                if (!graph[a[j]].count(b[j])) {
                    graph[a[j]].insert(b[j]);
                    indegree[b[j]]++;
                }
                break;
            }
        }
        if (j == len && a.size() > b.size()) return "";   // prefix violation
    }
    queue<char> q;
    for (auto& [c, d] : indegree) if (d == 0) q.push(c);
    string res;
    while (!q.empty()) {
        char c = q.front(); q.pop();
        res += c;
        for (char nxt : graph[c])
            if (--indegree[nxt] == 0) q.push(nxt);
    }
    return res.size() == graph.size() ? res : "";        // cycle → ""
}

• Complexity: O(total characters) time, O(1) space (alphabet ≤ 26).
• Pitfall: ① build only one edge from the first differing char, then break; ② the prefix violation (a longer word before its own prefix) must return "" — most-missed case; ③ register every character that appears into the graph (even edgeless ones); ④ an incomplete topological walk = a cycle = return "".

One Table to Remember It All

Pattern-Recognition Cheats

• "grid / 4-directional neighbors / regions" → DFS/BFS flood fill; remember to mark visited.
• "dependencies / ordering / can finish / scheduling" → topological sort, with cycle detection for free.
• "clone a graph / cyclic structure" → DFS/BFS + old→new hash map, register before recursing.
• "dynamic merging / same group / connected components" with incremental edges → Union-Find (path compression).
• "derive an order from a sorted sequence" → usually topological sort (nodes may be characters).

The essence of graph problems is just two steps: translate the prompt into "nodes + edges," then pick the right one of "traversal / topological sort / Union-Find." Translate correctly, choose the right tool, and the code is template-filling.