Leetcode 1101

class UnionFind:
    def __init__(self):
        self.parent = dict()
        self.rank = dict()
    
    def findRoot(self, i):
        if i not in self.parent:
            self.parent[i] = i
            self.rank[i] = 1
            return i
        while i != self.parent[i]:
            i = self.parent[i]
        return i

    def union(self, i , j):
        iRoot = self.findRoot(i)
        jRoot = self.findRoot(j)
        if iRoot == jRoot:
            return False
        # union the two sets
        if self.rank[iRoot] > self.rank[jRoot]:
            self.parent[jRoot] = iRoot
        elif self.rank[iRoot] < self.rank[jRoot]:
            self.parent[iRoot] = jRoot
        else:
            self.parent[iRoot] = jRoot
            self.rank[jRoot] += 1
        return True


class Solution:
    def earliestAcq(self, logs: List[List[int]], n: int) -> int:
        logs.sort()
        uf = UnionFind()
        count = n
        for ts, i, j in logs:
            if uf.union(i, j):
                count -= 1
            if count == 1:
                return ts
        return -1