跳至主要內容

1319. 连通网络的操作次数

ITCharge大约 2 分钟

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

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

题目大意

n 台计算机通过网线连接成一个网络,计算机的编号从 0n - 1。线缆用 comnnections 表示,其中 connections[i] = [a, b] 表示连接了计算机 ab

给定这个计算机网络的初始布线 connections,可以拔除任意两台直接相连的计算机之间的网线,并用这根网线连接任意一对未直接连接的计算机。现在要求:计算并返回使所有计算机都连通所需的最少操作次数。如果不可能,则返回 -1

解题思路

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

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

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

  • 如果 ab 已经在同一个集合中,说明该连接线多余,多余电线数 +1。
  • 如果 ab 不在一个集合中,则将其合并,则 ab 之间不再需要用额外的电线连接了,所以需要电线数 -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