Complete Guide to DFS and Graph Algorithms

Правка en1, от Nourhan_Abo-Heba, 2026-01-18 13:33:26

Table of Contents

  1. Graph Representation
  2. Basic DFS
  3. Connected Components
  4. Path Finding
  5. Tree DFS
  6. Bipartite Checking
  7. 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

  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!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Nourhan_Abo-Heba 2026-01-18 13:35:02 311
en1 Английский Nourhan_Abo-Heba 2026-01-18 13:33:26 7741 Initial revision (published)