DFS Traversal

Intuitionconnectivity is discovered one unseen vertex at a time

A connected component is the set of vertices reachable from one starting vertex. DFS follows edges as far as possible, so one DFS started at vertex start visits exactly every vertex connected to start and no vertex in another component. The visited array makes this statement stable even when the graph contains cycles, repeated edges, or several different paths to the same vertex.

A single DFS is not enough because the graph may be disconnected. Scan vertices from 0 upward; when the scan reaches an unseen vertex, it must be the smallest vertex of a new component, so starting DFS there also gives the components their required outer order. DFS itself may discover vertices in adjacency-list order, so sort the finished component before storing it.

Approachturn reachability into one scan and one DFS per component

1. 1Create an adjacency list with V buckets and add b to a's list and a to b's list for every edge [a, b], because an undirected edge must be traversable in both directions or some connected vertices will look unreachable.
2. 2Create a visited array of V false values and an empty answer, because each vertex needs one permanent membership decision and each discovered component needs its own output row.
3. 3Scan start from 0 through V - 1 and skip visited vertices, because the first unseen vertex is the smallest vertex of the next not-yet-recorded component; skipping it would lose that component's start.
4. 4For an unseen start, create a stack, push start, and mark it visited immediately, because marking on push prevents a cycle or repeated edge from putting the same vertex onto the stack several times.
5. 5While the stack is nonempty, pop one vertex, append it to the current component, and inspect every adjacency-list neighbor, because this visits all reachable vertices without revisiting vertices that already have a discovery mark.
6. 6For every unseen neighbor, mark it and push it, because the mark must happen before another pending path can encounter the same neighbor; delaying it until pop allows duplicates into the stack.
7. 7Sort the completed component and append it to answer, because DFS discovery order depends on edge-list order while the required row order is increasing; the outer scan already guarantees the required component order.

Complexitysorting is the only work beyond linear graph traversal

Annotated solutionC++ · iterative DFS · explicit stack with discovery-time marking

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges) {
        vector<vector<int>> adj(V);
        int usable = min(E, static_cast<int>(edges.size()));

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

        vector<int> visited(V, 0);
        vector<vector<int>> answer;

        for (int start = 0; start < V; ++start) {
            if (visited[start]) continue;

            vector<int> component;
            vector<int> stack;
            stack.push_back(start);
            visited[start] = 1;

            while (!stack.empty()) {
                int u = stack.back();
                stack.pop_back();
                component.push_back(u);

                for (int v : adj[u]) {
                    if (!visited[v]) {
                        visited[v] = 1;
                        stack.push_back(v);
                    }
                }
            }

            sort(component.begin(), component.end());
            answer.push_back(component);
        }

        return answer;
    }
};

The key placement is visited[v] = 1 when v is pushed, not when it is popped. Suppose two already discovered vertices both point to v. The first push reserves v immediately, so the second edge does nothing. This keeps the stack proportional to the number of vertices instead of allowing repeated edges and cycles to create duplicate pending entries.

The recursive alternativethe same traversal expressed through the call stack

A recursive DFS is a reasonable alternative because the graph's reachability rule naturally repeats the same operation for each neighbor. It is not asymptotically better: both versions take O(V + E) before sorting and use O(V) extra space in the worst case. The difference is where the pending work lives. The iterative version stores it in vector stack; recursion stores it in runtime call frames and can be less safe on a deep component.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
    void dfs(int u, const vector<vector<int>> &adj, vector<int> &visited, vector<int> &component) {
        visited[u] = 1;
        component.push_back(u);

        for (int v : adj[u]) {
            if (!visited[v]) {
                dfs(v, adj, visited, component);
            }
        }
    }

public:
    vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges) {
        vector<vector<int>> adj(V);
        int usable = min(E, static_cast<int>(edges.size()));

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

        vector<int> visited(V, 0);
        vector<vector<int>> answer;

        for (int start = 0; start < V; ++start) {
            if (visited[start]) continue;

            vector<int> component;
            dfs(start, adj, visited, component);
            sort(component.begin(), component.end());
            answer.push_back(component);
        }

        return answer;
    }
};

Common mistakeswrong code shapes that change reachability or output order