Table of Contents
- Graph Representation
- Basic DFS
- Connected Components
- Path Finding
- Tree DFS
- Bipartite Checking
- 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)
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
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
vector<array<int,3>> edges(m);
for(auto &[u,v,w] : edges){
cin >> u >> v >> w;
}
Basic DFS
Standard DFS Implementation
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
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.
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
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
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)
void dfsTree(int u, int par){
for(auto [v, w] : adj[u]){
if(v == par) continue;
dfsTree(v, u);
}
}
Finding Maximum Path to Leaf
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)
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
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
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.
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.
// 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
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
- Always check visited status before recursing to avoid infinite loops
- Use parent tracking in trees to avoid going back to parent
- Backtracking: Remove from path when DFS returns unsuccessfully
- Grid DFS: Check bounds first, then walls/visited, then mark visited
- Multiple components: Loop through all nodes and DFS unvisited ones
- 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!



