Skip to main content

Documentation Index

Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt

Use this file to discover all available pages before exploring further.

​
Graph Fundamentals

DFS vs BFS Graph Traversal

​
The Mental Model

Graphs model relationships. Cities connected by roads, friends in a social network, dependencies between tasks—all graphs. Mastering graphs means learning to see problems as nodes and edges, then applying the right traversal or algorithm. Analogy: A graph is a map. Nodes are locations; edges are roads connecting them. BFS is like a flood spreading outward from a point—it reaches all nearby locations first, then farther ones. DFS is like exploring a maze by always going deeper into one corridor until you hit a dead end, then backtracking. Both visit every reachable location, but the order is different, and that order matters for the problem you are solving.
Pattern Recognition Signals:
  • “Connected components” → DFS/BFS + Union-Find
  • “Shortest path” → BFS (unweighted) or Dijkstra (weighted)
  • “Cycle detection” → DFS with colors
  • “Topological ordering” → Kahn’s algorithm or DFS
  • “Bipartite check” → BFS/DFS coloring

​
Graph Representations

​
Adjacency List (Most Common in CP)

// Unweighted graph
int n, m;  // n nodes, m edges
vector<vector<int>> adj(n + 1);

for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);  // Remove for directed graph
}

// Weighted graph
vector<vector<pair<int, int>>> adj(n + 1);  // {neighbor, weight}

for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}

​
Edge List (For Kruskal’s MST)

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
    cin >> edges[i].u >> edges[i].v >> edges[i].w;
}

​
Adjacency Matrix (Dense Graphs, Floyd-Warshall)

vector<vector<int>> adj(n + 1, vector<int>(n + 1, INF));
for (int i = 1; i <= n; i++) adj[i][i] = 0;

for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u][v] = min(adj[u][v], w);
}
DFS explores as deep as possible before backtracking. It is the foundation for many graph algorithms: cycle detection, topological sort, SCC, bridges, and more. Time Complexity: O(V + E) — every node is visited once, and every edge is examined once. Space Complexity: O(V) for the visited array and recursion stack (stack depth = longest path from root). 
vector<bool> visited(n + 1, false);

void dfs(int u) {
    visited[u] = true;
    // Process node u here (pre-order)
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
    // Process node u here (post-order, useful for topo sort)
}

// Usage
for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        dfs(i);
        // Found a new connected component
    }
}

​
Iterative DFS (Avoids Stack Overflow)

void dfs(int start) {
    stack<int> st;
    st.push(start);
    
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        
        for (int v : adj[u]) {
            if (!visited[v]) {
                st.push(v);
            }
        }
    }
}
BFS explores all neighbors before going deeper. BFS finds shortest path in unweighted graphs. 
vector<int> dist(n + 1, -1);

void bfs(int start) {
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

​
BFS on Grid

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int bfs(vector<vector<int>>& grid, int sr, int sc, int tr, int tc) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> dist(n, vector<int>(m, -1));
    
    queue<pair<int, int>> q;
    q.push({sr, sc});
    dist[sr][sc] = 0;
    
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        
        if (r == tr && c == tc) return dist[r][c];
        
        for (int d = 0; d < 4; d++) {
            int nr = r + dx[d], nc = c + dy[d];
            
            if (nr >= 0 && nr < n && nc >= 0 && nc < m 
                && grid[nr][nc] == 0 && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    
    return -1;  // Unreachable
}

​
Pattern 1: Connected Components

Problem: Count connected components or check if two nodes are connected. 
int countComponents(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n + 1, false);
    int components = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);  // or bfs(i)
            components++;
        }
    }
    
    return components;
}
Codeforces Problems:
ProblemRatingLink
Building Roads1200CSES
Connected Components1000CF 977E

​
Pattern 2: Cycle Detection

​
In Undirected Graph

bool hasCycle(int u, int parent) {
    visited[u] = true;
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (hasCycle(v, u)) return true;
        } else if (v != parent) {
            return true;  // Back edge found
        }
    }
    
    return false;
}

​
In Directed Graph (Using Colors)

Analogy: Think of DFS as exploring a cave system. White nodes are unexplored rooms. Gray nodes are rooms you are currently inside (on your current path from the entrance). Black nodes are rooms you fully explored and left. If you find a passage to a gray room, you have found a cycle — you can walk in a circle back to where you are. Why three colors instead of two? In directed graphs, visiting an already-visited node does not always mean a cycle. If the node is black (fully processed), the edge goes to a separate branch — no cycle. Only a back edge to a gray (in-progress) node forms a cycle. 
// 0 = white (unvisited), 1 = gray (in current DFS path), 2 = black (fully processed)
vector<int> color(n + 1, 0);

bool hasCycle(int u) {
    color[u] = 1;  // Mark as in-progress
    
    for (int v : adj[u]) {
        if (color[v] == 1) return true;    // Back edge to ancestor = CYCLE
        if (color[v] == 0 && hasCycle(v)) return true;  // Unvisited: explore
        // color[v] == 2: cross/forward edge, no cycle
    }
    
    color[u] = 2;  // Fully processed
    return false;
}

// IMPORTANT: call for all nodes to handle disconnected components
// for (int i = 1; i <= n; i++)
//     if (color[i] == 0 && hasCycle(i)) { /* cycle found */ }

​
Pattern 3: Topological Sort

Problem: Order nodes so all edges go from earlier to later.

​
Kahn’s Algorithm (BFS)

Analogy: Think of university course prerequisites. You can only take a course when all its prerequisites are done. Kahn’s algorithm starts with courses that have no prerequisites (in-degree 0), “takes” them, and reduces the prerequisite count for dependent courses. When a course’s count drops to zero, it becomes available. If you process all courses this way and some remain, there is a circular dependency — a cycle. 
vector<int> topologicalSort(int n, vector<vector<int>>& adj) {
    // Step 1: Count incoming edges for each node
    vector<int> inDegree(n + 1, 0);
    
    for (int u = 1; u <= n; u++) {
        for (int v : adj[u]) {
            inDegree[v]++;
        }
    }
    
    // Step 2: Start with nodes that have no prerequisites
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    
    // Step 3: Process nodes, "removing" their outgoing edges
    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        
        for (int v : adj[u]) {
            if (--inDegree[v] == 0) {  // All prerequisites of v are done
                q.push(v);
            }
        }
    }
    
    // If not all nodes processed, a cycle prevented it
    if (order.size() != n) return {};  // Cycle exists
    return order;
}
// Time: O(V + E) -- each node and edge processed exactly once

​
DFS Approach

vector<int> order;
vector<bool> visited(n + 1, false);

void dfs(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v);
    }
    order.push_back(u);
}

// After all DFS calls
reverse(order.begin(), order.end());
Codeforces Problems:
ProblemRatingLink
Course Schedule1300CSES
Fox and Names1500CF 510C

​
Pattern 4: Bipartite Check

Problem: Can we 2-color the graph such that no edge connects same colors? 
bool isBipartite(int n, vector<vector<int>>& adj) {
    vector<int> color(n + 1, -1);
    
    for (int start = 1; start <= n; start++) {
        if (color[start] != -1) continue;
        
        queue<int> q;
        q.push(start);
        color[start] = 0;
        
        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;
                }
            }
        }
    }
    
    return true;
}
Key Insight: A graph is bipartite if and only if it has no odd-length cycles. This is because in a 2-coloring, every edge alternates colors, and a cycle of odd length would require a color to be adjacent to itself.
Contest tip: Many problems do not explicitly say “bipartite.” Look for signals like “divide into two groups such that all edges go between groups” or “2-colorable.” Also, any tree is bipartite (trees have no cycles at all).

​
Pattern 5: Flood Fill

Problem: Find connected regions in a grid (like paint bucket tool). 
void floodFill(vector<vector<int>>& grid, int r, int c, int newColor) {
    int oldColor = grid[r][c];
    if (oldColor == newColor) return;
    
    int n = grid.size(), m = grid[0].size();
    
    queue<pair<int, int>> q;
    q.push({r, c});
    grid[r][c] = newColor;
    
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m 
                && grid[nx][ny] == oldColor) {
                grid[nx][ny] = newColor;
                q.push({nx, ny});
            }
        }
    }
}

​
Common Mistakes

Mistake 1: 0 vs 1 Indexing Be consistent. In CP, 1-indexing is common for graphs.
vector<vector<int>> adj(n + 1);  // 1 to n
Mistake 2: Forgetting to Check All Components Not all nodes may be reachable from node 1:
for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        dfs(i);
    }
}
Mistake 3: Stack Overflow in DFS For graphs with 10^5+ nodes, use iterative DFS or increase stack size.
Mistake 4: Revisiting in BFS Mark visited when pushing to queue, not when popping. If you mark on pop, a node can be pushed multiple times by different neighbors, wasting time and potentially causing O(V^2) behavior on dense graphs.
// WRONG -- node u may be pushed many times before it is popped
int u = q.front(); q.pop();
if (visited[u]) continue;
visited[u] = true;

// CORRECT -- each node is pushed exactly once
for (int v : adj[u]) {
    if (!visited[v]) {
        visited[v] = true;  // Mark BEFORE pushing
        q.push(v);
    }
}

​
Practice Problems

​
Beginner (1000-1200)

ProblemPatternLink
Counting RoomsFlood fillCSES
Building RoadsComponentsCSES
LabyrinthBFS pathCSES

​
Intermediate (1200-1500)

ProblemPatternLink
Course ScheduleTopologicalCSES
Round TripCycle findingCSES
Building TeamsBipartiteCSES

​
Advanced (1500-1700)

ProblemPatternLink
Flight RoutesMulti-BFSCSES
Game RoutesDP on DAGCSES
Longest PathDAG DPCSES

​
Key Takeaways

DFS for Exploration

Use DFS for connectivity, cycles, and backtracking problems.

BFS for Shortest

BFS gives shortest path in unweighted graphs.

Adjacency List

Default representation in CP. O(V + E) space.

Color for State

Track visited/processing/done states for cycle detection.

​
Next Up

Chapter 14: Shortest Paths

Master Dijkstra, Bellman-Ford, and Floyd-Warshall for weighted shortest paths.