Quick Find

For this kind of implementation, we store the root vertexes of each node.

For example:

Would have the following values:

index             :  0 1 2 3 4 5
value (root node) : [0 0 0 3 3 3]

Implementation

The implementation would look something like:

class UnionFind:
    def __init__(self, n: int) -> None:
        self.n = n
        self.roots = [i for i in range(self.n)]

    def union(self, a: int, b: int) -> None:
        self._validate(a)
        self._validate(b)

        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return

        for i, root in enumerate(self.roots):
            if root == root_b:
                self.roots[i] = root_a

    def find(self, a: int) -> int:
        return self.roots[a]

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

    def _validate(self, a: int) -> None:
        assert 0 <= a < self.n

Usage

As explained earlier, let's apply the following data structure to Find if Path Exists in Graph.

from typing import List


class Solution:
    def validPath(
        self, n: int, edges: List[List[int]], source: int, destination: int
    ) -> bool:
        union_find = self.build_disjoint_set(n, edges)

        return union_find.connected(source, destination)

    def build_disjoint_set(self, n: int, edges: List[List[int]]) -> UnionFind:
        union_find = UnionFind(n)

        for a, b in edges:
            union_find.union(a, b)

        return union_find

Although this implementation is valid, we will get a Time Limit Exceeded for this problem.