2Brute2Best
🔥0
05

Graph connectivity (Graph BFS / DFS Sub-pattern)

Graphs given as edge lists, adjacency lists or matrices: is there a path, how many groups, can everything be reached, copy the graph.

Signals in the problem statement
  • ›

    "edges[i] = [a, b]" or "isConnected[i][j]"

  • ›

    "is there a valid path", "can you visit all rooms"

  • ›

    "number of provinces / components", "clone the graph"

What makes it different

Find if Path Exists builds the adjacency list (both directions) and runs one BFS. Keys and Rooms is directed: a key is a one-way edge. Number of Provinces reads neighbours from a matrix and counts DFS starts. Clone Graph uses a hash map from old node to its copy, which is also the visited set, so cycles don't loop forever.

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    Find if Path Exists in Graph
    Basic Anchor·LeetCode #1971
    Easy
  2. 2
    Keys and Rooms
    Basic Reinforcement·LeetCode #841
    Medium
  3. 3
    Number of Provinces
    Slight Variation·LeetCode #547
    Medium
  4. 4
    Clone Graph
    Medium·LeetCode #133
    Medium

Template

components-template.cpp
// 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;
}
Remember this · Graph BFS / DFS
Trigger
Grid of cells, islands, regions, "minimum steps", transformations between states, connected components.
Think
What is a node, what is an edge, and do I need the shortest path or just reachability?
Key question
How do I mark visited so I never process a node twice?
Implicit graph / state BFSBipartite / two-colouring