## Table of Contents↵
1. [Graph Representation](#graph-representation)↵
2. [Basic DFS](#basic-dfs)↵
3. [Connected Components](#connected-components)↵
4. [Path Finding](#path-finding)↵
5. [Tree DFS](#tree-dfs)↵
6. [Bipartite Checking](#bipartite-checking)↵
7. [Practice Problems](#practice-problems)↵
↵
---↵
## Graph Representation↵
↵
There are three main ways to represent graphs:↵
↵
| Method | Best For | Edge Check Time |↵
|--------|----------|----------------|↵
| Adjacency List | Sparse graphs | O(log V) |↵
| Adjacency Matrix | Dense graphs | O(1) |↵
| Edge List | Edge enumeration | O(log E) |↵
↵
### Adjacency List (Most Common)↵
```cpp↵
int n, m;↵
cin >> n >> m;↵
vector<vector<pair<int,int>>> adj(n+1);↵
for(int i = 0, u, v, w; i < m; i++){↵
cin >> u >> v >> w;↵
adj[u].emplace_back(v, w);↵
adj[v].emplace_back(u, w); // if undirected↵
}↵
```↵
↵
### Adjacency Matrix↵
```cpp↵
int n, m;↵
cin >> n >> m;↵
vector<vector<int>> adj(n+1, vector<int>(n+1, -1));↵
for(int i = 0, u, v, w; i < m; i++){↵
cin >> u >> v >> w;↵
adj[u][v] = w;↵
adj[v][u] = w; // if undirected↵
}↵
```↵
↵
### Edge List↵
```cpp↵
vector<array<int,3>> edges(m);↵
for(auto &[u,v,w] : edges){↵
cin >> u >> v >> w;↵
}↵
```↵
↵
---↵
↵
## Basic DFS↵
↵
### Standard DFS Implementation↵
```cpp↵
vector<vector<pair<int,int>>> adj;↵
vector<bool> vis;↵
↵
void dfs(int u){↵
cout << u << " ";↵
vis[u] = true;↵
for(auto [v, w] : adj[u]){↵
if(!vis[v]){↵
dfs(v);↵
}↵
}↵
}↵
```↵
↵
### Complete Setup↵
```cpp↵
int n, m; ↵
cin >> n >> m;↵
adj.assign(n+1, {});↵
vis.assign(n+1, false);↵
for(int i = 0, u, v, w; i < m; i++){↵
cin >> u >> v >> w;↵
adj[u].emplace_back(v, w);↵
adj[v].emplace_back(u, w);↵
}↵
dfs(1);↵
```↵
↵
---↵
↵
## Connected Components↵
↵
Count the number of separate components in an undirected graph.↵
↵
```cpp↵
int n, m; ↵
cin >> n >> m;↵
adj.assign(n+1, {});↵
vis.assign(n+1, false);↵
↵
for(int i = 0, u, v; i < m; i++){↵
cin >> u >> v;↵
adj[u].emplace_back(v);↵
adj[v].emplace_back(u);↵
}↵
↵
int components = 0;↵
for(int u = 1; u <= n; u++){↵
if(!vis[u]){↵
components++;↵
dfs(u);↵
}↵
}↵
cout << components << '\n';↵
```↵
↵
---↵
↵
## Path Finding↵
↵
### Finding Path with Specific Conditions↵
```cpp↵
vector<long long> path;↵
bool found = false;↵
long long tar;↵
↵
void dfs(long long cur){↵
if(cur > tar || found) return;↵
↵
path.push_back(cur);↵
↵
if(cur == tar){↵
found = true;↵
return;↵
}↵
↵
dfs(cur * 2);↵
dfs(cur * 10 + 1);↵
↵
if(!found)↵
path.pop_back(); // backtrack↵
}↵
```↵
↵
### Finding Path from Leaf↵
```cpp↵
unordered_map<long long, vector<long long>> adj;↵
unordered_map<long long, int> vis;↵
vector<long long> res;↵
unordered_map<long long, int> freq;↵
↵
void dfs(long long u){↵
vis[u] = 1;↵
res.push_back(u);↵
for(auto v : adj[u]){↵
if(!vis[v]){ ↵
dfs(v);↵
}↵
}↵
}↵
↵
// Find starting leaf (degree = 1)↵
long long start = -1;↵
for(auto it : freq){↵
if(it.second == 1){↵
start = it.first;↵
break;↵
}↵
}↵
↵
dfs(start);↵
for(auto it : res){↵
cout << it << " ";↵
}↵
```↵
↵
---↵
↵
## Tree DFS↵
↵
### DFS on Tree (with Parent Tracking)↵
```cpp↵
void dfsTree(int u, int par){↵
for(auto [v, w] : adj[u]){↵
if(v == par) continue;↵
dfsTree(v, u);↵
}↵
}↵
```↵
↵
### Finding Maximum Path to Leaf↵
```cpp↵
int ans = 0;↵
↵
void dfs(int par, int u, int sum){↵
if(adj[u].size() == 1){ // leaf node↵
ans = max(ans, sum);↵
}↵
for(auto [v, w] : adj[u]){ ↵
if(v != par){↵
dfs(u, v, sum + w); ↵
}↵
}↵
}↵
```↵
↵
### Conditional Tree Traversal (e.g., Consecutive Cats Problem)↵
```cpp↵
int ans = 0;↵
vector<int> cat;↵
int m;↵
↵
void dfs(int u, int par, int consecutiveCats){↵
if(cat[u] == 1)↵
consecutiveCats++;↵
else↵
consecutiveCats = 0;↵
↵
if(consecutiveCats > m)↵
return;↵
↵
int children = 0;↵
for(int v : adj[u]){↵
if(v != par){↵
children++;↵
dfs(v, u, consecutiveCats);↵
}↵
}↵
↵
if(children == 0){ // leaf↵
ans++;↵
}↵
}↵
```↵
↵
---↵
↵
## Bipartite Checking↵
↵
Check if a graph can be divided into two groups where no two nodes in the same group are connected.↵
↵
### Method 1: Using Depth Levels↵
```cpp↵
unordered_map<int, vector<int>> adj;↵
map<int, int> ans;↵
map<int, int> vis;↵
int flag = 1;↵
↵
void dfs(int u, int j){↵
vis[u] = 1;↵
ans[u] = (j % 2 == 1) ? 1 : 2;↵
↵
for(auto v : adj[u]){↵
if(!vis[v]){↵
dfs(v, j + 1);↵
}↵
else if(ans[v] == ans[u]){↵
flag = 0;↵
return;↵
}↵
}↵
}↵
```↵
↵
### Method 2: Using Color Array↵
```cpp↵
int flag = 0;↵
unordered_map<int, int> color;↵
↵
void dfs(int u, vector<vector<int>>& adj, map<int, int>& vis, int i){↵
vis[u] = 1;↵
color[u] = (i % 2 == 1) ? 1 : 2;↵
↵
for(auto v : adj[u]){↵
if(!vis[v]){↵
dfs(v, adj, vis, i + 1);↵
}↵
if(vis[v] && color[u] == color[v]){↵
flag = 1;↵
return;↵
}↵
}↵
}↵
↵
// Check all components↵
for(int k = 1; k <= n; k++){↵
if(!vis[k])↵
dfs(k, adj, vis, 1);↵
}↵
```↵
↵
---↵
↵
## Practice Problems↵
↵
### 1. CSES — Counting Rooms↵
↵
**Problem:** Count the number of rooms in a grid where `#` is wall and `.` is floor.↵
↵
**Key Idea:** Mark all connected floor cells in the same room as visited. Each DFS call represents one room.↵
↵
```cpp↵
int n, m;↵
vector<vector<char>> vec;↵
↵
void dfs(int i, int j){↵
if(i >= n || j >= m || i < 0 || j < 0) return;↵
if(vec[i][j] == '#' || vec[i][j] == 'v') return;↵
↵
if(vec[i][j] == '.'){↵
vec[i][j] = 'v';↵
}↵
↵
dfs(i+1, j);↵
dfs(i-1, j);↵
dfs(i, j+1);↵
dfs(i, j-1);↵
}↵
↵
int main(){↵
cin >> n >> m;↵
vec.resize(n, vector<char>(m));↵
↵
for(int i = 0; i < n; i++)↵
for(int j = 0; j < m; j++)↵
cin >> vec[i][j];↵
↵
int rooms = 0;↵
for(int i = 0; i < n; i++){↵
for(int j = 0; j < m; j++){↵
if(vec[i][j] == '.'){↵
rooms++;↵
dfs(i, j);↵
}↵
}↵
}↵
↵
cout << rooms << '\n';↵
}↵
```↵
↵
### 2. CSES — Building Teams↵
↵
**Problem:** Divide students into two teams such that no two friends are on the same team.↵
↵
```cpp↵
// Use the bipartite checking code from above↵
// If flag == 0, output "IMPOSSIBLE"↵
// Otherwise, output the team assignments from ans/color array↵
```↵
↵
### 3. Finding Cycle in Graph↵
↵
```cpp↵
int ans = INT_MAX;↵
int n;↵
↵
void dfs(int u, int par, int i, int c){↵
for(auto [v, w] : adj[u]){↵
if(v == 1){↵
if(i + 1 == n){↵
ans = min(ans, c + w);↵
}↵
}↵
else if(v != par){↵
dfs(v, u, i + 1, c + w);↵
}↵
}↵
}↵
```↵
↵
---↵
↵
## Tips and Tricks↵
↵
1. **Always check visited status** before recursing to avoid infinite loops↵
2. **Use parent tracking** in trees to avoid going back to parent↵
3. **Backtracking:** Remove from path when DFS returns unsuccessfully↵
4. **Grid DFS:** Check bounds first, then walls/visited, then mark visited↵
5. **Multiple components:** Loop through all nodes and DFS unvisited ones↵
6. **Bipartite:** Color nodes with alternating colors, check for conflicts↵
↵
---↵
↵
## Complexity Analysis↵
↵
- **Time Complexity:** O(V + E) where V is vertices and E is edges↵
- **Space Complexity:** O(V) for visited array and recursion stack↵
↵
Happy Coding!



