连通网络的操作次数

标签: 深度优先搜索 广度优先搜索 并查集 图

难度: Medium

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。 

示例 1：

输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。

示例 2：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2

示例 3：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。

示例 4：

输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出：0

提示：

  • 1 <= n <= 10^5
  • 1 <= connections.length <= min(n*(n-1)/2, 10^5)
  • connections[i].length == 2
  • 0 <= connections[i][0], connections[i][1] < n
  • connections[i][0] != connections[i][1]
  • 没有重复的连接。
  • 两台计算机不会通过多条线缆连接。

Submission

运行时间: 65 ms

内存: 29.8 MB

# 并查集模板
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.n = n
        # 当前连通分量数目
        self.setCount = n
    
    def findset(self, x: int) -> int:
        if self.parent[x] == x:
            return x
        self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]
    
    def unite(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x
        self.size[x] += self.size[y]
        self.setCount -= 1
        return True
    
    def connected(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        return x == y

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1
        
        uf = UnionFind(n)
        for x, y in connections:
            uf.unite(x, y)
        
        return uf.setCount - 1

Explain

这道题目使用并查集来处理计算机的连通性。首先，初始化一个并查集，每台计算机自成一个连通分量。对于每一对给定的连接，尝试将它们合并。如果两台计算机已经处于同一连通分量中，则该操作无效；否则，合并操作将减少一个连通分量。最终，如果存在少于n-1条线缆，无法将所有计算机连接起来，返回-1。否则，需要的最少操作次数等于最终连通分量数减一，因为将m个连通分量完全连接需要至少m-1次操作。

时间复杂度: O(m)

空间复杂度: O(n)

# 并查集模板
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))  # 每个节点的父节点
        self.size = [1] * n  # 每个连通分量的大小
        self.n = n  # 节点总数
        self.setCount = n  # 连通分量的初始数量
    
    def findset(self, x: int) -> int:
        # 寻找根节点，并应用路径压缩优化
        if self.parent[x] == x:
            return x
        self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]
    
    def unite(self, x: int, y: int) -> bool:
        # 合并两个节点所在的连通分量
        x, y = self.findset(x), self.findset(y)
        if x == y:
            return False
        # 按大小合并，保持小树接到大树下面
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x
        self.size[x] += self.size[y]
        self.setCount -= 1  # 减少一个连通分量
        return True
    
    def connected(self, x: int, y: int) -> bool:
        # 判断两个节点是否连通
        x, y = self.findset(x), self.findset(y)
        return x == y

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        # 检查是否有足够的线缆
        if len(connections) < n - 1:
            return -1  # 线缆不足以连接所有计算机
        
        uf = UnionFind(n)
        # 尝试合并所有给定的连接
        for x, y in connections:
            uf.unite(x, y)
        
        # 需要的操作数等于连通分量数减一
        return uf.setCount - 1

Explore

在并查集中，初始化每个节点的父节点为其自身主要是为了表示每个节点最初都是独立的连通分量。这种设计简化了并查集的管理，因为每个节点在开始时都是自己的一个连通分量，不与其他节点连通。这样，合并和查询操作都可以在这个初始状态下统一进行，无需额外的条件判断。此外，这也便于使用路径压缩等优化技术，因为每个节点最初都指向自己，路径压缩时修改路径上的指向更加直接和高效。

按大小合并，即将较小的连通分量合并到较大的连通分量下，是一种优化策略，称为按秩合并。这种策略的优势在于它可以帮助保持树的高度尽可能低，从而减少了查找根节点操作的时间复杂度。当树的高度较低时，任何从子节点到根节点的路径都较短，因此查找效率更高。这最终导致整个并查集的操作效率提升，特别是在频繁执行查找和合并操作的场景中。

这个结论基于图论中的基本性质，即在一个包含n个节点的图中，要形成一个连通图至少需要n-1条边。这是因为每添加一条边可以连接两个原本不连通的部分，从而最少需要n-1条边来确保所有节点都连通。如果线缆数量少于n-1，即使最优配置这些线缆，也无法使所有计算机连通，因为边的数量不足以连接所有独立的部分。

路径压缩是并查集优化技术中的一种，其实现方式是在执行`findset`函数寻找节点的根节点时，将查找路径上的每个节点直接连接到根节点上。这样做的目的是减少后续操作中查找根节点的路径长度，从而提高查找效率。具体实现时，当一个节点的父节点不是它自身时，递归地寻找并更新其父节点，直到找到根节点。这种优化显著减少了查找时间，特别是在并查集较大或查找操作较频繁的情况下。