DFS (Connectivity)

Key Signals & Indicators

• Requires traversing every node or path in the graph
• Finding connected components, cycle detection, path existence
• Backtracking searches in grids/mazes

// C++ Graph DFS Connectivity Template
#include <vector>
#include <unordered_set>

void dfs(int u, const std::vector<std::vector<int>>& adjList, std::unordered_set<int>& visited) {
    visited.insert(u);
    
    for (int v : adjList[u]) {
        if (visited.find(v) == visited.end()) {
            dfs(v, adjList, visited); // Recurse on unvisited neighbor
        }
    }
}

int countComponents(int n, const std::vector<std::vector<int>>& adjList) {
    std::unordered_set<int> visited;
    int components = 0;
    for (int i = 0; i < n; ++i) {
        if (visited.find(i) == visited.end()) {
            dfs(i, adjList, visited);
            components++; // Component complete
        }
    }
    return components;
}