Graph BFS / DFS Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

// Flood fill: every unvisited land cell starts one DFS; everything it reaches is one island.
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};

int sink(vector<vector<char>>& grid, int r, int c) {
    int R = grid.size(), C = grid[0].size();
    if (r < 0 || c < 0 || r >= R || c >= C || grid[r][c] != '1') return 0;
    grid[r][c] = '0';                             // mark BEFORE exploring, so no cell is counted twice
    int size = 1;
    for (int d = 0; d < 4; d++) size += sink(grid, r + dr[d], c + dc[d]);
    return size;                                  // island size (Max Area); ignore it to just count
}

int countIslands(vector<vector<char>>& grid) {
    int islands = 0;
    for (int r = 0; r < (int)grid.size(); r++)
        for (int c = 0; c < (int)grid[0].size(); c++)
            if (grid[r][c] == '1') { islands++; sink(grid, r, c); }
    return islands;
}

// Multi-source BFS: every source goes in the queue at distance 0, then all spread together.
vector<vector<int>> nearestSource(const vector<vector<int>>& grid) {   // 1 = source, 0 = open, -1 = wall
    int R = grid.size(), C = grid[0].size();
    vector<vector<int>> dist(R, vector<int>(C, -1));                     // -1 = not reached yet
    queue<pair<int, int>> q;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (grid[r][c] == 1) { dist[r][c] = 0; q.push({r, c}); }
    int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C || grid[nr][nc] == -1 || dist[nr][nc] != -1) continue;
            dist[nr][nc] = dist[r][c] + 1;        // first time reached = nearest source
            q.push({nr, nc});
        }
    }
    return dist;
}

// Shortest path in an unweighted grid: BFS from the start; the first time we pop the target is the answer.
int shortestPath(const vector<vector<int>>& grid, pair<int, int> start, pair<int, int> target) {  // 0 = open, 1 = wall
    int R = grid.size(), C = grid[0].size();
    if (grid[start.first][start.second] || grid[target.first][target.second]) return -1;
    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int, int>> q;
    dist[start.first][start.second] = 0;
    q.push(start);
    int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        if (make_pair(r, c) == target) return dist[r][c];
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C || grid[nr][nc] || dist[nr][nc] != -1) continue;
            dist[nr][nc] = dist[r][c] + 1;        // mark when PUSHED, not when popped
            q.push({nr, nc});
        }
    }
    return -1;
}

// State BFS: nodes are states (strings here), neighbours are generated on the fly.
int minMoves(const string& start, const string& goal, const unordered_set<string>& blocked) {
    if (blocked.count(start)) return -1;
    unordered_map<string, int> dist{{start, 0}};
    queue<string> q;
    q.push(start);
    while (!q.empty()) {
        string s = q.front(); q.pop();
        if (s == goal) return dist[s];
        for (int i = 0; i < (int)s.size(); i++)
            for (int step : {1, 9}) {                       // one wheel up or down (Open the Lock)
                string t = s;
                t[i] = char('0' + (t[i] - '0' + step) % 10);
                if (blocked.count(t) || dist.count(t)) continue;
                dist[t] = dist[s] + 1;
                q.push(t);
            }
    }
    return -1;
}

// Connectivity: adjacency list + visited; each new DFS start is a new component.
int countComponents(int n, const vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }  // undirected: both ways
    vector<bool> seen(n, false);
    int components = 0;
    for (int s = 0; s < n; s++) {
        if (seen[s]) continue;
        components++;
        vector<int> stack{s};                    // iterative DFS: no recursion depth limit
        seen[s] = true;
        while (!stack.empty()) {
            int u = stack.back(); stack.pop_back();
            for (int v : adj[u]) if (!seen[v]) { seen[v] = true; stack.push_back(v); }
        }
    }
    return components;
}

// Two-colouring: give a node colour 0, its neighbours colour 1, and so on; a same-colour edge = not bipartite.
bool isBipartite(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> color(n, -1);
    for (int s = 0; s < n; s++) {                // every component, not just node 0
        if (color[s] != -1) continue;
        color[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) { color[v] = 1 - color[u]; q.push(v); }
                else if (color[v] == color[u]) return false;   // an odd cycle
            }
        }
    }
    return true;
}