from typing import List
# 我們使用并查集來做這道題，一共N臺電腦的話，至少需要n-1根線，
# 并查集模板
class UnionFind:
def __init__(self):
#記錄每一個節點的父節點
self.size = 0
self.father = {}
def find(self,x):
"""尋找根節點，路徑壓縮"""
root = x
while self.father[root] != None:
root = self.father[root]
while x != root:
oraginal_father = self.father[x]
self.father[x] = root
x = oraginal_father
return root
def merge(self,x,y):
"""合并兩個并查集"""
root_x,root_y = self.find(x),self.find(y)
if root_x != root_y:
self.father[root_y] = x
self.size -= 1
def is_connected(self,x,y):
"""判斷兩個節點是否相連"""
return self.find(x) == self.find(y)
def add(self,x):
"""添加新節點"""
if x not in self.father:
self.father[x] = None
self.size += 1
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
# 首先判斷是否滿足所有電腦都相連的條件，
if len(connections) < n - 1:
return -1
# 定義一個并查集，
res = UnionFind()
# 將所有電腦添加到并查集中，
for i in range(n):
res.add(i)
# 判斷兩個電腦是否相連，也就是是否同屬于一個根節點，
# 如果不是的話，那么我們就將這兩個電腦相連，
# 最后就可以求出來冗余的連線，然后撥動他們，就可以將所有的電腦相連了，
for nums in connections:
if not res.is_connected(nums[0],nums[1]):
res.merge(nums[0],nums[1])
# 因為size是總的電腦數，跟連線數不一樣，
return res.size - 1
# A = Solution()
# print(A.makeConnected(4,[[0,1],[0,2],[1,2]]))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/251407.html
標籤：Python