Problem Description

Given an undirected graph with n vertices numbered from 0 to n-1, and a list of edges, determine weather a valid path exists between the source vertex and the destination vertex.

Solution Approach

This problem can be efficiently solved using the Union-Find (Disjoint Set Union) data structuer. The key idea is to treat each edge as a connection that merges two sets of vertices. After processing all edges, we can check if the source and destination vertices belong to the same set.

Union-Find Operations

1. Initialization: Create a parent array where each vertex is its own parenet (forms standalone sets)
2. Find: Locate the root/representative of a set using path compression for optimization
3. Union: Merge two sets by connecting one root to another
4. Connected Check: Determine if two vertices share the same root

Path Compression

During the find operation, we recursively traverse up the tree and update each node's parent directly to the root. This optimization significantly reduces future lookup times.

Implementation

public class Solution {
    private int[] parent;
    
    /**
     * Determines if a valid path exists between source and destination vertices.
     * 
     * @param n number of vertices
     * @param edges array of edges representing connections
     * @param source starting vertex
     * @param destination ending vertex
     * @return true if path exists, false otherwise
     */
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        parent = new int[n];
        initializeSets();
        
        for (int[] edge : edges) {
            union(edge[0], edge[1]);
        }
        
        return areConnected(source, destination);
    }
    
    /**
     * Initialize each vertex as its own set with itself as parent.
     */
    private void initializeSets() {
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }
    
    /**
     * Find the root vertex of the set containing the given vertex.
     * Uses path compression for optimization.
     * 
     * @param vertex the vertex to find root for
     * @return the root representative
     */
    private int find(int vertex) {
        if (vertex == parent[vertex]) {
            return vertex;
        }
        // Path compression: point directly to root
        parent[vertex] = find(parent[vertex]);
        return parent[vertex];
    }
    
    /**
     * Merge the sets containing two vertices.
     * 
     * @param a first vertex
     * @param b second vertex
     */
    private void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        
        if (rootA == rootB) {
            return; // Already in the same set
        }
        // Connect rootB to rootA
        parent[rootB] = rootA;
    }
    
    /**
     * Check if two vertices are in the same connected component.
     * 
     * @param a first vertex
     * @param b second vertex
     * @return true if connected, false otherwise
     */
    private boolean areConnected(int a, int b) {
        return find(a) == find(b);
    }
}

Complexity Analysis

• Time Complexity: O(n + m × α(n)) where n is the number of vertices, m is the number of edges, and α(n) is the inverse Ackermann function (practically constant)
• Space Complexity: O(n) for storing the parent array

Key Points

1. Union-Find provides nearly constant-time amortized operations for merging sets and checking connectivity
2. Path compression makes the find operation faster by flattening the tree structure
3. The algorithm processes each edge once, making it efficient for large graphs