解決問題所依循的程序

以Dynamic Connectivity問題為例

問題的描述

輸入為一連串由一對對正整數所組成的序列，例如(2, 10), (0, 3), (4, 5)…，每個正整數代表的是某種類型的物件（可以代表社交網絡中的一個人、網絡中的一個節點等等），而一對正整數 (3, 10) 的意思是，將 3 與 10 「連在一起。

實際應用

  • 網絡分析
  • 程式語言中變數名稱的相等性
  • 數學上的集合

開始製定Union-Find API

1
2
3
4
5
6
7
8
9
10
11
class UF:
    def __init__(self, n):
        self.id = [i for i in range(0, n)]
        
    def connected(self, a , b):
    
    # 找出位置  的元素
    def find(self, p):
    
    # 將 p 和 q 連在一起
    def union(self, p, q):

第一種實作: Quick-Find