跳至主要內容

1319. 连通网络的操作次数

ITCharge大约 3 分钟

1319. 连通网络的操作次数open in new window

  • 标签:深度优先搜索、广度优先搜索、并查集、图
  • 难度:中等

题目链接

题目大意

描述nn 台计算机通过网线连接成一个网络,计算机的编号从 00n1n - 1。线缆用 comnnectionscomnnections 表示,其中 connections[i]=[a,b]connections[i] = [a, b] 表示连接了计算机 aabb

给定这个计算机网络的初始布线 connectionsconnections,可以拔除任意两台直接相连的计算机之间的网线,并用这根网线连接任意一对未直接连接的计算机。

要求:计算并返回使所有计算机都连通所需的最少操作次数。如果不可能,则返回 1-1

说明

  • 1n1051 \le n \le 10^5
  • 1connections.lengthmin(n×(n1)2,105)1 \le connections.length \le min( \frac{n \times (n-1)}{2}, 10^5)
  • connections[i].length==2connections[i].length == 2
  • 0connections[i][0],connections[i][1]<n0 \le connections[i][0], connections[i][1] < n
  • connections[i][0]!=connections[i][1]connections[i][0] != connections[i][1]
  • 没有重复的连接。
  • 两台计算机不会通过多条线缆连接。

示例

  • 示例 1:
输入:n = 4, connections = [[0,1],[0,2],[1,2]]
输出:1
解释:拔下计算机 12 之间的线缆,并将它插到计算机 13 上。
  • 示例 2:
输入:n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出:2

解题思路

思路 1:并查集

nn 台计算机至少需要 n1n - 1 根线才能进行连接,如果网线的数量少于 n1n - 1,那么就不可能将其连接。接下来计算最少操作次数。

nn 台计算机看做是 nn 个节点,每条网线看做是一条无向边。维护两个变量:多余电线数 removeCountremoveCount、需要电线数 needConnectCountneedConnectCount。初始 removeCount=1,needConnectCount=n1removeCount = 1, needConnectCount = n - 1

遍历网线数组,将相连的节点 aabb 利用并查集加入到一个集合中(调用 union 操作)。

  • 如果 aabb 已经在同一个集合中,说明该连接线多余,多余电线数加 11
  • 如果 aabb 不在一个集合中,则将其合并,则 aabb 之间不再需要用额外的电线连接了,所以需要电线数减 11

最后,判断多余的电线数是否满足需要电线数,不满足返回 1-1,如果满足,则返回需要电线数。

思路 1:代码

class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        self.parent[root_x] = root_y
        return True

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        union_find = UnionFind(n)
        removeCount = 0
        needConnectCount = n - 1
        for connection in connections:
            if union_find.union(connection[0], connection[1]):
                needConnectCount -= 1
            else:
                removeCount += 1

        if removeCount < needConnectCount:
            return -1
        return needConnectCount

思路 1:复杂度分析

  • 时间复杂度O(m×α(n))O(m \times \alpha(n)),其中 mm 是数组 connectionsconnections 的长度,α\alpha 是反 Ackerman 函数。
  • 空间复杂度O(n)O(n)