> ## 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

> Master graph representations, traversals, and fundamental graph algorithms

# Graph Fundamentals

<img src="https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/graph-traversal-dfs-bfs.svg?fit=max&auto=format&n=AEOaWh79Ur7CdHHv&q=85&s=6d781e26e6acb14eb83fc040d485dad4" alt="DFS vs BFS Graph Traversal" width="1080" height="1080" data-path="images/courses/cp/graph-traversal-dfs-bfs.svg" />

## 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.

<Note>
  **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
</Note>

***

## Graph Representations

### Adjacency List (Most Common in CP)

```cpp theme={null}
// 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)

```cpp theme={null}
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)

```cpp theme={null}
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).

```cpp theme={null}
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)

```cpp theme={null}
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.**

```cpp theme={null}
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

```cpp theme={null}
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.

```cpp theme={null}
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](https://cses.fi/problemset/task/1666)               |
| Connected Components | 1000   | [CF 977E](https://codeforces.com/problemset/problem/977/E) |

***

## Pattern 2: Cycle Detection

### In Undirected Graph

```cpp theme={null}
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.

```cpp theme={null}
// 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.

```cpp theme={null}
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

```cpp theme={null}
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](https://cses.fi/problemset/task/1679)               |
| Fox and Names   | 1500   | [CF 510C](https://codeforces.com/problemset/problem/510/C) |

***

## Pattern 4: Bipartite Check

**Problem**: Can we 2-color the graph such that no edge connects same colors?

```cpp theme={null}
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.

<Tip>
  **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).
</Tip>

***

## Pattern 5: Flood Fill

**Problem**: Find connected regions in a grid (like paint bucket tool).

```cpp theme={null}
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

<Warning>
  **Mistake 1: 0 vs 1 Indexing**
  Be consistent. In CP, 1-indexing is common for graphs.

  ```cpp theme={null}
  vector<vector<int>> adj(n + 1);  // 1 to n
  ```
</Warning>

<Warning>
  **Mistake 2: Forgetting to Check All Components**
  Not all nodes may be reachable from node 1:

  ```cpp theme={null}
  for (int i = 1; i <= n; i++) {
      if (!visited[i]) {
          dfs(i);
      }
  }
  ```
</Warning>

<Warning>
  **Mistake 3: Stack Overflow in DFS**
  For graphs with 10^5+ nodes, use iterative DFS or increase stack size.
</Warning>

<Warning>
  **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.

  ```cpp theme={null}
  // 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);
      }
  }
  ```
</Warning>

***

## Practice Problems

### Beginner (1000-1200)

| Problem        | Pattern    | Link                                         |
| -------------- | ---------- | -------------------------------------------- |
| Counting Rooms | Flood fill | [CSES](https://cses.fi/problemset/task/1192) |
| Building Roads | Components | [CSES](https://cses.fi/problemset/task/1666) |
| Labyrinth      | BFS path   | [CSES](https://cses.fi/problemset/task/1193) |

### Intermediate (1200-1500)

| Problem         | Pattern       | Link                                         |
| --------------- | ------------- | -------------------------------------------- |
| Course Schedule | Topological   | [CSES](https://cses.fi/problemset/task/1679) |
| Round Trip      | Cycle finding | [CSES](https://cses.fi/problemset/task/1669) |
| Building Teams  | Bipartite     | [CSES](https://cses.fi/problemset/task/1668) |

### Advanced (1500-1700)

| Problem       | Pattern   | Link                                         |
| ------------- | --------- | -------------------------------------------- |
| Flight Routes | Multi-BFS | [CSES](https://cses.fi/problemset/task/1195) |
| Game Routes   | DP on DAG | [CSES](https://cses.fi/problemset/task/1681) |
| Longest Path  | DAG DP    | [CSES](https://cses.fi/problemset/task/1680) |

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="DFS for Exploration" icon="magnifying-glass">
    Use DFS for connectivity, cycles, and backtracking problems.
  </Card>

  <Card title="BFS for Shortest" icon="route">
    BFS gives shortest path in unweighted graphs.
  </Card>

  <Card title="Adjacency List" icon="list">
    Default representation in CP. O(V + E) space.
  </Card>

  <Card title="Color for State" icon="palette">
    Track visited/processing/done states for cycle detection.
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 14: Shortest Paths" icon="arrow-right" href="/courses/competitive-programming/14-shortest-paths">
  Master Dijkstra, Bellman-Ford, and Floyd-Warshall for weighted shortest paths.
</Card>