684. Redundant Connection

Question: Redundant Connection

Solution

想法：用 Union and Find

1. 將 edges 的兩個 nodes 一個一個連接並建立起來
2. 連接的方式
1. 先找到 node1 跟 node2 的 parent： p1, p2
2. 查看 p1, p2 是否相同
1. 相同：產生 loop，return [n1, n2]
2. 不相同：連結在一起
1. 連結時，要依照 node 的數量，數量少的接到多的上
2. 如下圖 2 node 的 parent 是 1(p1); 3 node 的 parent 是自己(p2)，又 p1 的數量(2)比 p2 的數量(1)多，所以 p2 要接到 p1 上
   
   
   p1 的數量也會從原本的 2 變成 3
   

   
   因此要多一個地方儲存 node 們的數量

class Solution:

def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:

parent = [i for i in range(len(edges) + 1)]

rank = [1] * (len(edges) + 1)

def find_parent(n):

p = parent[n]

while p != parent[p]:

parent[n] = parent[p]

p = parent[parent[p]]

return p

def union(n1, n2):

p1, p2 = find_parent(n1), find_parent(n2)

if p1 == p2:

return False

elif rank[p1] > rank[p2]:

parent[p2] = parent[p1]

rank[p1] += rank[p2]

else:

parent[p1] = parent[p2]

rank[p2] += rank[p1]

return True

for n1, n2 in edges:

if not union(n1, n2):

return [n1, n2]

Video Solution