1319. 连通网络的操作次数
大约 2 分钟
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,如果满足,则返回需要电线数。
代码
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