# Complete Guide to DFS and Graph Algorithms
Разница между en1 и en2, 311 символ(ов) изменены
↵
## 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 &mdash; 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 &mdash; 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! 

История

 
 
 
 
Правки
 
 
  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)