Graph Fundamentals

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: Depth-First Search

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: Breadth-First Search

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:

Problem	Rating	Link
Building Roads	1200	CSES
Connected Components	1000	CF 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:

Problem	Rating	Link
Course Schedule	1300	CSES
Fox and Names	1500	CF 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)

Problem	Pattern	Link
Counting Rooms	Flood fill	CSES
Building Roads	Components	CSES
Labyrinth	BFS path	CSES

Intermediate (1200-1500)

Problem	Pattern	Link
Course Schedule	Topological	CSES
Round Trip	Cycle finding	CSES
Building Teams	Bipartite	CSES

Advanced (1500-1700)

Problem	Pattern	Link
Flight Routes	Multi-BFS	CSES
Game Routes	DP on DAG	CSES
Longest Path	DAG DP	CSES

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.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Graph Fundamentals

Graph Fundamentals

The Mental Model

Graph Representations

Adjacency List (Most Common in CP)

Edge List (For Kruskal’s MST)

Adjacency Matrix (Dense Graphs, Floyd-Warshall)

DFS: Depth-First Search

Iterative DFS (Avoids Stack Overflow)

BFS: Breadth-First Search

BFS on Grid

Pattern 1: Connected Components

Pattern 2: Cycle Detection

In Undirected Graph

In Directed Graph (Using Colors)

Pattern 3: Topological Sort

Kahn’s Algorithm (BFS)

DFS Approach

Pattern 4: Bipartite Check

Pattern 5: Flood Fill

Common Mistakes

Practice Problems

Beginner (1000-1200)

Intermediate (1200-1500)

Advanced (1500-1700)

Key Takeaways

DFS for Exploration

BFS for Shortest

Adjacency List

Color for State

Next Up

Chapter 14: Shortest Paths

​Graph Fundamentals

​The Mental Model

​Graph Representations

​Adjacency List (Most Common in CP)

​Edge List (For Kruskal’s MST)

​Adjacency Matrix (Dense Graphs, Floyd-Warshall)

​DFS: Depth-First Search

​Iterative DFS (Avoids Stack Overflow)

​BFS: Breadth-First Search

​BFS on Grid

​Pattern 1: Connected Components

​Pattern 2: Cycle Detection

​In Undirected Graph

​In Directed Graph (Using Colors)

​Pattern 3: Topological Sort

​Kahn’s Algorithm (BFS)

​DFS Approach

​Pattern 4: Bipartite Check

​Pattern 5: Flood Fill

​Common Mistakes

​Practice Problems

​Beginner (1000-1200)

​Intermediate (1200-1500)

​Advanced (1500-1700)

​Key Takeaways

DFS for Exploration

BFS for Shortest

Adjacency List

Color for State

​Next Up

Chapter 14: Shortest Paths

Graph Fundamentals

The Mental Model

Graph Representations

Adjacency List (Most Common in CP)

Edge List (For Kruskal’s MST)

Adjacency Matrix (Dense Graphs, Floyd-Warshall)

DFS: Depth-First Search

Iterative DFS (Avoids Stack Overflow)

BFS: Breadth-First Search

BFS on Grid

Pattern 1: Connected Components

Pattern 2: Cycle Detection

In Undirected Graph

In Directed Graph (Using Colors)

Pattern 3: Topological Sort

Kahn’s Algorithm (BFS)

DFS Approach

Pattern 4: Bipartite Check

Pattern 5: Flood Fill

Common Mistakes

Practice Problems

Beginner (1000-1200)

Intermediate (1200-1500)

Advanced (1500-1700)

Key Takeaways

Next Up