DFS (Depth-First Search)

Concept

DFS explores a graph by going as deep as possible along each branch before backtracking. It uses recursion (or a stack) to dive into unvisited neighbors. By unmarking nodes after returning, it can find all paths or check reachability.

When to Use

  • ▸Checking if a path exists between two nodes
  • ▸Counting all distinct paths in a graph
  • ▸Detecting cycles in a graph
  • ▸Exploring all connected components
  • ▸Backtracking problems where you need to try all possibilities

Intuition

Imagine exploring a maze by always picking the leftmost corridor. You walk until you hit a dead end, then backtrack to the last intersection and try the next corridor. DFS does exactly this — it commits fully to one direction, backtracks when stuck, and tries another. Unmarking visited nodes on return lets you discover every possible route.

Complexity

Time
O(V + E) for single visit, O(V! ) for all paths
Space
O(V) recursion stack

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

// --- Pathfinding DFS (does path exist?) ---
bool dfs(int n, int target, vector<bool> &visited, vector<vector<int>> &adj){
    if(n == target) return true;
    if(visited[n] == true) return false;

    visited[n] = true;

    bool check = false;
    for(int x : adj[n]){
        check = (check||dfs(x, target, visited, adj));
    }

    visited[n] = false;

    return check;
}

// --- Count All Paths DFS ---
int countPaths(int n, int target, vector<bool> &visited, vector<vector<int>> &adj){
    if(n == target) return 1;
    if(visited[n] == true) return 0;

    visited[n] = true;

    int check = 0;
    for(int x : adj[n]){
        check += countPaths(x, target, visited, adj);
    }

    visited[n] = false;

    return check;
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    int node, edges, target;
    cin >> node >> edges >> target;

    vector<vector<int>> adj(node);
    vector<bool> visited(node, false);

    for(int i = 0; i < edges; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b]. push_back(a);
    }

    bool ans = dfs(0, target, visited, adj);
    if(ans) printf("YES");
    else printf("NO");

    return 0;
}

// Sample Input:
// 6 7 5
// 0 1
// 0 2
// 1 3
// 2 3
// 3 4
// 4 5
// 2 5
//
// Sample Output:
// YES