JZX轻语：简

LeetCode 1319 - 连通网络的操作次数

发表于2024年07月27日

#图论 #并查集

基于图论一个重要的定理：如果一个图有n个节点，至少需要n-1条边才能使得所有节点连通。如果边的数量小于n-1，那么一定有节点无法连通。此外，如果有k个连通分量，那么至少需要k-1条边才能使得所有节点连通。因此，首先需要判断边的数量是否足够，如果不够，直接返回-1。然后，使用并查集来统计连通分量的数量，最后返回最少操作次数(即需要将这些连通分量连接起来的最少边数)为连通分量数-1。

class UnionSet:
    def __init__(self, n):
        self.pa = list(range(n))
        self.component_len = n

    def find(self, x: int):
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]

    def unite(self, x: int, y: int):
        px, py = self.find(x), self.find(y)
        self.pa[px] = py
        if px != py:
            self.component_len -= 1
            
    def __len__(self):
        return self.component_len
            
            
class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1

        uset = UnionSet(n)
        for u, v in connections:
            uset.unite(u, v)
        return len(uset) - 1

闪念标签：LC

题目链接：https://leetcode.cn/problems/number-of-operations-to-make-network-connected/