Find if Path Exists in Graph — Editorial

Opening the reading…

Intuitionconnectivity matters more than the exact route

A path exists between two nodes exactly when they are in the same connected component. The individual order of edges does not matter: if an edge joins u and v, every node reachable from u becomes reachable from v as well. So instead of searching for one particular route, you can maintain groups of nodes that have become connected while processing the edges.

Disjoint set union stores those groups compactly. Each node starts in its own set. For an edge [u, v], find the representative of each endpoint and merge the two sets when their representatives differ. After every edge has been processed, source and destination have a path between them precisely when find(source) and find(destination) return the same representative.

Approachbuild components once, then compare two roots

Create parent and size arrays for all n nodes, making every node its own parent and giving every set size 1, because no connectivity is known before an edge is processed.

Implement find with path halving: repeatedly move a node toward its root and point it to its grandparent, because flattening visited paths keeps later connectivity checks fast.

Implement unite by finding both roots and returning when they already match, because attaching a set to itself changes nothing and can corrupt the parent structure if handled as a merge.

When the roots differ, attach the smaller set below the larger root and update the larger size, because balanced trees keep parent chains short even before path compression helps.

Process every edge with unite on its two endpoints, because each edge is exactly the evidence that its endpoints belong to one connected component.

Return whether find(source) equals find(destination), because equal representatives mean both nodes belong to the same component and therefore have a path between them.

Complexitynear-constant connectivity operations

MEASURE	BOUND	WHY
Time	O((n + m) alpha(n))	Initialising the n parent entries costs O(n). Each of the m unions performs a constant number of find operations, and union by size plus path halving makes their total amortized cost O((n + m) alpha(n)), with no edge processed more than once.
Space	O(n) extra	The parent and size arrays store two integers per node, so working memory grows with n; the returned value is a single boolean and contributes no output storage. The bound does not worsen for a particular graph shape because union by size keeps the maintained trees logarithmic before path compression.

Here n is the number of nodes, m is the number of edges, and alpha(n) is the inverse Ackermann function.

Annotated solutionC++ · disjoint set union · component membership answers the query

CPPBuild all connected components with union by size and path halving, then compare the two representatives.

#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<int> parent(n);
        vector<int> size(n, 1);

        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }

        function<int(int)> find = [&](int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        };

        auto unite = [&](int a, int b) {
            int rootA = find(a);
            int rootB = find(b);
            if (rootA == rootB) {
                return;
            }

            if (size[rootA] < size[rootB]) {
                swap(rootA, rootB);
            }
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        };

        for (auto& edge : edges) {
            unite(edge[0], edge[1]);
        }

        return find(source) == find(destination);
    }
};

The important separation is between a node and its representative. parent[x] may point to another node rather than directly to the root, so every comparison of connectivity must go through find. The merge also changes only roots: attaching rootB below rootA preserves the forest invariant that every parent chain eventually ends at a self-parenting representative.

The search alternativeBFS or DFS is often clearer for one query

CPPAlternative: build an adjacency list and search outward from source with BFS.

#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        vector<bool> visited(n, false);
        queue<int> pending;
        pending.push(source);
        visited[source] = true;

        while (!pending.empty()) {
            int node = pending.front();
            pending.pop();
            if (node == destination) {
                return true;
            }

            for (int next : graph[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    pending.push(next);
                }
            }
        }

        return false;
    }
};

BFS and DFS are a different arrangement, not a strict optimisation. They use O(n + m) time and O(n + m) extra space because the adjacency list stores every undirected edge twice, while union-find uses O(n) extra space and avoids storing adjacency lists. Search can stop as soon as destination is reached, so it is a natural choice when you have one query and want the route-searching idea to be explicit.