什么是不相交集數(shù)據(jù)結構？

????????如果兩個集合沒有任何共同元素，則它們被稱為不相交集，集合的交集為空集。

????????存儲不重疊或不相交元素子集的數(shù)據(jù)結構稱為不相交集合數(shù)據(jù)結構。不相交集合數(shù)據(jù)結構支持以下操作：

1、將新集合添加到不相交集合中。

2、使用聯(lián)合操作將不相交集合并為單個不相交集。

3、使用“查找”操作查找不相交集的代表。

4、檢查兩個集合是否不相交。?

考慮這樣一個情況，有許多人需要執(zhí)行以下任務：

? ? ? ? 1、添加新的友誼關系，即一個人 x 成為另一個人 y 的朋友，即向集合中添加新元素。

? ? ? ? 2、判斷個體x 是否是個體 y 的朋友（直接或間接朋友）

例子：?

我們有 10 個人，比如 a、b、c、d、e、f、g、h、i、j

以下是需要添加的關系：
a <-> b ??
b <-> d?
c <-> f?
c <-> i?
j <-> e?
g <-> j

給定查詢，例如 a 是否是 d 的朋友。我們基本上需要創(chuàng)建以下 4 個組，并在組項之間保持快速訪問的連接：
G1 = {a, b, d}?
G2 = {c, f, i}?
G3 = {e, g, j}?
G4 = {h}

判斷 x 和 y 是否屬于同一組，即判斷 x 和 y 是否是直接/間接朋友。

????????根據(jù)個體所屬的組別，將個體劃分為不同的集合。此方法稱為不相交集合并集，它維護不相交集合的集合，每個集合由其成員之一表示。

要回答上述問題，需要考慮兩個關鍵點：

? ? ? ? 1、如何解析集合？最初，所有元素都屬于不同的集合。在處理給定的關系后，我們選擇一個成員作為代表。選擇代表的方法有很多種，一種簡單的方法是選擇最大的索引。

? ? ? ? 2、檢查兩個人是否在同一組中？如果兩個人的代表相同，那么他們就會成為朋友。

使用的數(shù)據(jù)結構包括：?

????????數(shù)組：整數(shù)數(shù)組稱為Parent[]。如果我們處理N 個項目，則數(shù)組的第 i 個元素代表第 i 個項目。更準確地說，Parent[] 數(shù)組的第 i 個元素是第 i 個項目的父級。這些關系創(chuàng)建一個或多個虛擬樹。

????????樹：它是一個不相交集。如果兩個元素在同一棵樹中，那么它們就在同一個不相交集。每棵樹的根節(jié)點（或最頂端節(jié)點）稱為集合的代表。每個集合始終有一個唯一的代表。識別代表的一個簡單規(guī)則是，如果“i”是集合的代表，則Parent[i] = i。如果 i 不是其集合的代表，則可以通過沿樹向上移動直到找到代表來找到它。

不相交集合數(shù)據(jù)結構上的操作：
????????查找
????????聯(lián)合

1. 查找：
????????可以通過遞歸遍歷父數(shù)組直到找到其自身的父節(jié)點來實現(xiàn)。

# Finds the representative of the set?
# that i is an element of?
??
def find(i):?
??
? ? # If i is the parent of itself?
? ? if (parent[i] == i):?
??
? ? ? ? # Then i is the representative of?
? ? ? ? # this set?
? ? ? ? return i?
? ? else:?
??
? ? ? ? # Else if i is not the parent of?
? ? ? ? # itself, then i is not the?
? ? ? ? # representative of his set. So we?
? ? ? ? # recursively call Find on its parent?
? ? ? ? return find(parent[i])?
??
?# The code is contributed by Nidhi goel?

時間復雜度：這種方法效率低下，在最壞的情況下可能需要 O(n) 時間。

2. 聯(lián)合：?

????????它以兩個元素作為輸入，并使用查找操作找到它們的集合的代表，最后將其中一棵樹（代表集合）放在另一棵樹的根節(jié)點下。

# Unites the set that includes i?
# and the set that includes j?
??
def union(parent, rank, i, j):?
? ? # Find the representatives?
? ? # (or the root nodes) for the set?
? ? # that includes i?
? ? irep = find(parent, i)?
? ? ??
? ? # And do the same for the set?
? ? # that includes j?
? ? jrep = find(parent, j)?
? ? ??
? ? # Make the parent of i’s representative?
? ? # be j’s ?representative effectively?
? ? # moving all of i’s set into j’s set)?
? ? ??
? ? parent[irep] = jrep??

時間復雜度：這種方法效率低下，在最壞的情況下可能導致長度為 O（n）的樹。

優(yōu)化（按等級/大小合并和路徑壓縮）：

?? ?效率在很大程度上取決于哪棵樹連接到另一棵樹。有兩種方法可以實現(xiàn)。第一種是按等級聯(lián)合，它將樹的高度視為一個因素；第二種是按大小聯(lián)合，它將樹的大小視為一個因素，同時將一棵樹連接到另一棵樹。此方法與路徑壓縮一起提供了幾乎恒定時間的復雜性。

路徑壓縮（對 Find() 的修改）：

?? ?它通過壓縮樹的高度來加速數(shù)據(jù)結構。這可以通過在Find操作中插入一個小的緩存機制來實現(xiàn)。查看代碼了解更多詳細信息：

# ?Finds the representative of the set that i?
# is an element of.?
??
??
def find(i):?
??
? ? # If i is the parent of itself?
? ? if Parent[i] == i:?
??
? ? ? ? # Then i is the representative ?
? ? ? ? return i?
? ? else:?
??
? ? ? ? # Recursively find the representative.?
? ? ? ? result = find(Parent[i])?
??
? ? ? ? # We cache the result by moving i’s node ?
? ? ? ? # directly under the representative of this?
? ? ? ? # set?
? ? ? ? Parent[i] = result?
? ? ? ??
? ? ? ? # And then we return the result?
? ? ? ? return result?
??
# The code is contributed by Arushi ?Jindal. ??

時間復雜度：平均每次調(diào)用為 O(log n)。

按等級合并：

?? ?首先，我們需要一個新的整數(shù)數(shù)組，名為rank[] 。此數(shù)組的大小與父數(shù)組Parent[]相同。如果 i 代表一個集合，則rank[i]就是代表該集合的樹的高度。 現(xiàn)在回想一下，在 Union 操作中，將兩棵樹中的哪一棵移動到另一棵之下并不重要?，F(xiàn)在我們要做的是最小化結果樹的高度。如果我們要合并兩棵樹（或集合），我們將它們稱為左和右，那么這一切都取決于左的等級和右的等級。?

?? ??? ?1、如果左邊的等級小于右邊的等級，那么最好將左邊移到右邊的下方，因為這不會改變右邊的等級（而將右邊移到左邊的下方會增加高度）。同樣，如果右邊的等級小于左邊的等級，那么我們應該將右邊移到左邊的下方。

?? ??? ?2、如果等級相等，那么哪棵樹位于另一棵樹之下并不重要，但結果的等級始終比樹的等級大一。

class DisjointSet:?
? ? def __init__(self, size):?
? ? ? ? self.parent = [i for i in range(size)]?
? ? ? ? self.rank = [0] * size?
??
? ? # Function to find the representative (or the root node) of a set?
? ? def find(self, i):?
? ? ? ? # If i is not the representative of its set, recursively find the representative?
? ? ? ? if self.parent[i] != i:?
? ? ? ? ? ? self.parent[i] = self.find(self.parent[i]) ?# Path compression?
? ? ? ? return self.parent[i]?
??
? ? # Unites the set that includes i and the set that includes j by rank?
? ? def union_by_rank(self, i, j):?
? ? ? ? # Find the representatives (or the root nodes) for the set that includes i and j?
? ? ? ? irep = self.find(i)?
? ? ? ? jrep = self.find(j)?
??
? ? ? ? # Elements are in the same set, no need to unite anything?
? ? ? ? if irep == jrep:?
? ? ? ? ? ? return
??
? ? ? ? # Get the rank of i's tree?
? ? ? ? irank = self.rank[irep]?
??
? ? ? ? # Get the rank of j's tree?
? ? ? ? jrank = self.rank[jrep]?
??
? ? ? ? # If i's rank is less than j's rank?
? ? ? ? if irank < jrank:?
? ? ? ? ? ? # Move i under j?
? ? ? ? ? ? self.parent[irep] = jrep?
? ? ? ? # Else if j's rank is less than i's rank?
? ? ? ? elif jrank < irank:?
? ? ? ? ? ? # Move j under i?
? ? ? ? ? ? self.parent[jrep] = irep?
? ? ? ? # Else if their ranks are the same?
? ? ? ? else:?
? ? ? ? ? ? # Move i under j (doesn't matter which one goes where)?
? ? ? ? ? ? self.parent[irep] = jrep?
? ? ? ? ? ? # Increment the result tree's rank by 1?
? ? ? ? ? ? self.rank[jrep] += 1
??
? ? def main(self):?
? ? ? ? # Example usage?
? ? ? ? size = 5
? ? ? ? ds = DisjointSet(size)?
??
? ? ? ? # Perform some union operations?
? ? ? ? ds.union_by_rank(0, 1)?
? ? ? ? ds.union_by_rank(2, 3)?
? ? ? ? ds.union_by_rank(1, 3)?
??
? ? ? ? # Find the representative of each element?
? ? ? ? for i in range(size):?
? ? ? ? ? ? print(f"Element {i} belongs to the set with representative {ds.find(i)}")?
??
??
# Creating an instance and calling the main method?
ds = DisjointSet(size=5)?
ds.main()?

按大小合并：

?? ?同樣，我們需要一個新的整數(shù)數(shù)組，名為size[] 。此數(shù)組的大小與父數(shù)組Parent[]相同。如果 i 代表一個集合，則size[i]是代表該集合的樹中元素的數(shù)量。 現(xiàn)在我們將兩棵樹（或集合）合并起來，我們將它們稱為左樹和右樹，在這種情況下，一切都取決于左樹（或集合）的大小和右樹（或集合）的大小。

?? ??? ?1、如果左邊的尺寸小于右邊的尺寸，那么最好將左邊移到右邊下方，并將右邊的尺寸增加左邊的尺寸。同樣，如果右邊的尺寸小于左邊的尺寸，那么我們應該將右邊移到左邊下方，并將左邊的尺寸增加右邊的尺寸。

?? ??? ?2、如果尺寸相等，那么哪棵樹位于另一棵樹下都沒有關系。

# Python program for the above approach?
class UnionFind:?
? ? def __init__(self, n):?
? ? ? ? # Initialize Parent array?
? ? ? ? self.Parent = list(range(n))?
??
? ? ? ? # Initialize Size array with 1s?
? ? ? ? self.Size = [1] * n?
??
? ? # Function to find the representative (or the root node) for the set that includes i?
? ? def find(self, i):?
? ? ? ? if self.Parent[i] != i:?
? ? ? ? ? ? # Path compression: Make the parent of i the root of the set?
? ? ? ? ? ? self.Parent[i] = self.find(self.Parent[i])?
? ? ? ? return self.Parent[i]?
??
? ? # Unites the set that includes i and the set that includes j by size?
? ? def unionBySize(self, i, j):?
? ? ? ? # Find the representatives (or the root nodes) for the set that includes i?
? ? ? ? irep = self.find(i)?
??
? ? ? ? # And do the same for the set that includes j?
? ? ? ? jrep = self.find(j)?
??
? ? ? ? # Elements are in the same set, no need to unite anything.?
? ? ? ? if irep == jrep:?
? ? ? ? ? ? return
??
? ? ? ? # Get the size of i’s tree?
? ? ? ? isize = self.Size[irep]?
??
? ? ? ? # Get the size of j’s tree?
? ? ? ? jsize = self.Size[jrep]?
??
? ? ? ? # If i’s size is less than j’s size?
? ? ? ? if isize < jsize:?
? ? ? ? ? ? # Then move i under j?
? ? ? ? ? ? self.Parent[irep] = jrep?
??
? ? ? ? ? ? # Increment j's size by i's size?
? ? ? ? ? ? self.Size[jrep] += self.Size[irep]?
? ? ? ? # Else if j’s size is less than i’s size?
? ? ? ? else:?
? ? ? ? ? ? # Then move j under i?
? ? ? ? ? ? self.Parent[jrep] = irep?
??
? ? ? ? ? ? # Increment i's size by j's size?
? ? ? ? ? ? self.Size[irep] += self.Size[jrep]?
??
# Example usage?
n = 5
unionFind = UnionFind(n)?
??
# Perform union operations?
unionFind.unionBySize(0, 1)?
unionFind.unionBySize(2, 3)?
unionFind.unionBySize(0, 4)?
??
# Print the representative of each element after unions?
for i in range(n):?
? ? print("Element {}: Representative = {}".format(i, unionFind.find(i)))?
??
# This code is contributed by Susobhan Akhuli

輸出
元素 0：代表 = 0
元素 1：代表 = 0
元素 2：代表 = 2
元素 3：代表 = 2
元素 4：代表 = 0

時間復雜度：O（log n），無路徑壓縮。

下面是具有路徑壓縮和按等級合并的不相交集的完整實現(xiàn)。

# Python3 program to implement Disjoint Set Data?
# Structure.?
??
class DisjSet:?
? ? def __init__(self, n):?
? ? ? ? # Constructor to create and?
? ? ? ? # initialize sets of n items?
? ? ? ? self.rank = [1] * n?
? ? ? ? self.parent = [i for i in range(n)]?
??
??
? ? # Finds set of given item x?
? ? def find(self, x):?
? ? ? ? ??
? ? ? ? # Finds the representative of the set?
? ? ? ? # that x is an element of?
? ? ? ? if (self.parent[x] != x):?
? ? ? ? ? ? ??
? ? ? ? ? ? # if x is not the parent of itself?
? ? ? ? ? ? # Then x is not the representative of?
? ? ? ? ? ? # its set,?
? ? ? ? ? ? self.parent[x] = self.find(self.parent[x])?
? ? ? ? ? ? ??
? ? ? ? ? ? # so we recursively call Find on its parent?
? ? ? ? ? ? # and move i's node directly under the?
? ? ? ? ? ? # representative of this set?
??
? ? ? ? return self.parent[x]?
??
??
? ? # Do union of two sets represented?
? ? # by x and y.?
? ? def Union(self, x, y):?
? ? ? ? ??
? ? ? ? # Find current sets of x and y?
? ? ? ? xset = self.find(x)?
? ? ? ? yset = self.find(y)?
??
? ? ? ? # If they are already in same set?
? ? ? ? if xset == yset:?
? ? ? ? ? ? return
??
? ? ? ? # Put smaller ranked item under?
? ? ? ? # bigger ranked item if ranks are?
? ? ? ? # different?
? ? ? ? if self.rank[xset] < self.rank[yset]:?
? ? ? ? ? ? self.parent[xset] = yset?
??
? ? ? ? elif self.rank[xset] > self.rank[yset]:?
? ? ? ? ? ? self.parent[yset] = xset?
??
? ? ? ? # If ranks are same, then move y under?
? ? ? ? # x (doesn't matter which one goes where)?
? ? ? ? # and increment rank of x's tree?
? ? ? ? else:?
? ? ? ? ? ? self.parent[yset] = xset?
? ? ? ? ? ? self.rank[xset] = self.rank[xset] + 1
??
# Driver code?
obj = DisjSet(5)?
obj.Union(0, 2)?
obj.Union(4, 2)?
obj.Union(3, 1)?
if obj.find(4) == obj.find(0):?
? ? print('Yes')?
else:?
? ? print('No')?
if obj.find(1) == obj.find(0):?
? ? print('Yes')?
else:?
? ? print('No')?
??
# This code is contributed by ng24_7.?

?輸出

Yes
No

時間復雜度：創(chuàng)建 n 個單項集的時間為 O(n)。兩種技術（路徑壓縮和按等級/大小合并）的時間復雜度將達到接近常數(shù)時間。事實證明，最終的 攤銷時間復雜度為 O(α(n))，其中 α(n) 是逆阿克曼函數(shù)，其增長非常穩(wěn)定（當 n<10 600 ? 時，它甚至不會超過）。

空間復雜度： O（n），因為我們需要在不相交集數(shù)據(jù)結構中存儲 n 個元素。