发表于 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 题目链接