unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 1971: Find if Path Exists in Graph

There is a path between source and destination if and only if the two vertices belong to the same connected component (cc). With Union-Find, we start with n connected components — one per vertex. As we union the two ends of edges, the number of connected components goes down. At the end, we check if source and destination belong to the same cc.

If there are m edges, time: \mathcal{O}(m \cdot \lg^*{n}), space: \mathcal{O}(n).

class UnionFind:
    def __init__(self, n):
        self.parent_of, self.rank_of = {}, {}
        for u in range(n):
            self.parent_of[u] = u
            self.rank_of[u] = 0

    def __compress_path(self, u, root):
        while u != (p := self.parent_of[u]):
            self.parent_of[u] = root
            u = p

    def __find(self, u):
        root = u
        while root != (p := self.parent_of[root]):
            root = p
        self.__compress_path(u, root)

        return root
    
    def union(self, u, v):
        root_u = self.__find(u)
        root_v = self.__find(v)
        if root_u == root_v:
            return
        
        rank_u = self.rank_of[root_u]
        rank_v = self.rank_of[root_v]
        if rank_u == rank_v:
            self.parent_of[root_u] = root_v
            self.rank_of[root_v] += 1
            return
        
        if rank_u < rank_v:
            self.parent_of[root_u] = root_v
        else:
            self.parent_of[root_v] = root_u
        
    
    def has_path(self, u, v):
        root_u = self.__find(u)
        root_v = self.__find(v)

        return root_u == root_v


class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        uf = UnionFind(n)
        for u, v in edges:
            uf.union(u, v)
        
        return uf.has_path(source, destination)

tanvirdotzaman

,

Leave a comment