本文共 1526 字，大约阅读时间需要 5 分钟。

题目：（中等）

标签：并查集、排序

解法一：

class DSU:    def __init__(self, n: int):        self._n = n        self._array = [i for i in range(n)]        self._size = [1] * n        self._group_num = n    def find(self, i: int) -> int:        """查询i所在的连通分支:O(1)"""        if self._array[i] != i:            self._array[i] = self.find(self._array[i])        return self._array[i]    def union(self, i: int, j: int) -> bool:        """合并i和j所属的连通分支:O(1)"""        i, j = self.find(i), self.find(j)        if i != j:            self._group_num -= 1            if self._size[i] >= self._size[j]:                self._array[j] = i                self._size[i] += self._size[j]            else:                self._array[i] = j                self._size[j] += self._size[i]            return True        else:            return False    def is_connected(self, i: int, j: int) -> bool:        return self.find(i) == self.find(j)    @property    def group_num(self):        """计算连通分支数量:O(1)"""        return self._group_num    @property    def max_group_size(self):        """计算最大连通分支包含的数量:O(N)"""        import collections        return max(collections.Counter(self._array).values())class Solution:    def earliestAcq(self, logs: List[List[int]], n: int) -> int:        logs.sort()        dsu = DSU(n)        for date, a, b in logs:            dsu.union(a, b)            if dsu.group_num == 1:                return date        return -1

转载地址：http://dxkcf.baihongyu.com/