Union-Find 演算法

不交集集合 (Disjoint Set)，也常被稱為 Union-Find 演算法。它用於管理一系列不重疊的集合，並支援兩個主要操作：

• Union (聯集)：將兩個集合合併成一個。
• Find (尋找)：確定某個元素屬於哪個集合，通常透過尋找其集合的「代表元素」或「根」來實現。

 parent = list(range(10))

print(parent)

def find(x):

  if parent[x]!=x:

    parent[x]=find(parent[x])

  return parent[x]

def union(x,y):

  rootX= find(x)

  rootY= find(y)

  if rootX!=rootY:

    parent[rootX]=rootY

    

def show_sets():

  groups = {}

  for i in range(len(parent)):

    root = find(i)

    if root not in groups:

      groups[root]=[]

    groups[root].append(i)

  for g in groups.values():

    print('group:',g)

    

show_sets()

print()

union(1,2)

union(2,3)

union(3,9)

show_sets()

Output:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

group: [0]

group: [1]

group: [2]

group: [3]

group: [4]

group: [5]

group: [6]

group: [7]

group: [8]

group: [9]

group: [0]

group: [1, 2, 3, 9]

group: [4]

group: [5]

group: [6]

group: [7]

group: [8]