1319. 连通网络的操作次数 #

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

题目大意 #

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

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

解题思路 #

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

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

遍历网线数组，将相连的节点 a 和 b 利用并查集加入到一个集合中（调用 union 操作）。

如果 a 和 b 已经在同一个集合中，说明该连接线多余，多余电线数 +1。
如果 a 和 b 不在一个集合中，则将其合并，则 a 和 b 之间不再需要用额外的电线连接了，所以需要电线数 -1。

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

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


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