Complete Guide to DFS and Graph Algorithms

Revision en2, by Nourhan_Abo-Heba, 2026-01-18 13:35:02

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

  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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Nourhan_Abo-Heba 2026-01-18 13:35:02 311
en1 English Nourhan_Abo-Heba 2026-01-18 13:33:26 7741 Initial revision (published)