DFS Applications

March 2026 · 18 min read

DFS is not just a traversal. It is a framework. The structure of the DFS tree (discovery/finish times, back edges, stack state) gives us tools to solve many graph problems. This post covers the most important applications you will encounter in competitive programming and interviews.

Cycle Detection

Directed Graphs

A directed graph has a cycle if and only if DFS finds a back edge: an edge from the current node to a node that is still in the recursion stack (colored gray).

enum Color { WHITE, GRAY, BLACK };
vector<Color> color(n, WHITE);
bool hasCycle = false;

void dfs(int u) {
    color[u] = GRAY;
    for (int v : adj[u]) {
        if (color[v] == GRAY) {
            hasCycle = true;  // back edge found
            return;
        }
        if (color[v] == WHITE) {
            dfs(v);
            if (hasCycle) return;
        }
    }
    color[u] = BLACK;
}

Undirected Graphs

In undirected graphs, every edge appears twice (u-v and v-u). The edge back to the parent is not a back edge. Track the parent to avoid false positives.

bool dfsCycleUndirected(int u, int parent, vector<vector<int>>& adj,
                         vector<bool>& visited) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (dfsCycleUndirected(v, u, adj, visited))
                return true;
        } else if (v != parent) {
            return true;  // visited and not parent = cycle
        }
    }
    return false;
}

Connected Components

A connected component is a maximal set of nodes where every pair is reachable from every other. Finding all connected components: iterate over all nodes, run DFS from each unvisited node.

int components = 0;
vector<int> comp(n, -1);  // which component each node belongs to

for (int i = 0; i < n; i++) {
    if (comp[i] == -1) {
        // DFS marking all reachable nodes with current component id
        dfsLabel(i, components, adj, comp);
        components++;
    }
}
// components = total number of connected components

Flood Fill / Number of Islands

A grid version of connected components. Each "island" (connected group of land cells) is a component. DFS from any unvisited land cell marks the entire island.

Three islands: top-left (4 cells), top-right (1 cell), bottom cluster (1 + 2 cells).

int numIslands(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int count = 0;

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (grid[i][j] == '1') {
                dfsFlood(grid, i, j);
                count++;
            }
    return count;
}

void dfsFlood(vector<vector<char>>& grid, int r, int c) {
    if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size())
        return;
    if (grid[r][c] != '1') return;
    grid[r][c] = '0';  // mark visited by sinking
    dfsFlood(grid, r+1, c);
    dfsFlood(grid, r-1, c);
    dfsFlood(grid, r, c+1);
    dfsFlood(grid, r, c-1);
}

Topological Sort via DFS

Topological sort orders the vertices of a DAG such that for every edge u → v, u appears before v. DFS gives this naturally: the reverse of the post-order (finish order) is a valid topological sort.

vector<int> topoOrder;

void dfs(int u) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v]) dfs(v);
    topoOrder.push_back(u);  // add on finish
}

// After running DFS from all unvisited nodes:
reverse(topoOrder.begin(), topoOrder.end());
// topoOrder is now a valid topological ordering

Why does this work? When dfs(u) finishes, all of u's descendants are already in the list. Reversing puts u before all its descendants, satisfying the topological constraint.

Bipartite Check

A graph is bipartite if its vertices can be colored with two colors such that no two adjacent vertices share a color. DFS (or BFS) with two-coloring detects this.

bool isBipartite(int n, vector<vector<int>>& adj) {
    vector<int> color(n, -1);  // -1 = uncolored

    for (int i = 0; i < n; i++) {
        if (color[i] != -1) continue;
        // BFS/DFS from node i
        queue<int> q;
        q.push(i);
        color[i] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;  // same color neighbors
                }
            }
        }
    }
    return true;
}

Summary