1971. Find if Path Exists in Graph

Breadth-First Search Depth-First Search Union Find Graph

Problem Overview

Undirected graph connectivity: determine whether destination is reachable from source using any sequence of edges.

Intuition

Undirected graph connectivity: determine whether destination is reachable from source using any sequence of edges. BFS or DFS from source is sufficient; Union-Find also works if you prefer offline connectivity.

Algorithm

1Build adjacency list from bi-directional edges.
2BFS: queue starting with source, visited set.
3Dequeue node u; if u == destination return true.
4Enqueue unvisited neighbors of u.
5If queue empties without reaching destination, return false.

Example Walkthrough

Input: n=3, edges=[[0,1],[1,2],[2,0]], source=0, destination=2

1.From 0 reach 1 and 2 via edges — destination found.

Output: true

Common Pitfalls

•Edges are undirected — add both directions to adjacency list.
•Source equals destination should return true immediately.
•No edge weights — plain reachability, not shortest path.

1971.cs

// Approach: Union-Find; union all edges; return true if source and destination are in same component.
// Time: O(E α(n)) Space: O(n)

public class Solution
{
    public bool ValidPath(int n, int[][] edges, int source, int destination)
    {
        DisjointSet ds = new DisjointSet(n);

        foreach (int[] edge in edges)
        {
            int u = edge[0];
            int v = edge[1];
            ds.unionBySize(u, v);
        }

        return ds.findUPar(source) == ds.findUPar(destination);
    }
}

class DisjointSet
{
    List<int> parent = new List<int>();
    List<int> size = new List<int>();

    public DisjointSet(int n)
    {
        for (int i = 0; i < n; i++)
        {
            parent.Add(i);
            size.Add(1);
        }
    }

    public int findUPar(int node)
    {
        if (node == parent[node])
            return node;

        return parent[node] = findUPar(parent[node]);
    }

    public void unionBySize(int u, int v)
    {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);

        if (ulp_u == ulp_v)
            return;

        if (size[ulp_u] < size[ulp_v])
        {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }
        else
        {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
}

Was this solution helpful?