圖論之并查集—

介紹

秩是什么

例子——快速入門

例題

使用路徑壓縮，不使用秩合并

使用路徑壓縮和秩合并

無向圖和有向圖

介紹

并查集是一種用于處理不相交集合的合并與查詢問題的數據結構。它主要涉及以下基本概念和操作：

基本概念：

集合：并查集中的集合是由一組元素組成的，這些元素具有相同的屬性或特征，集合之間相互不相交。
代表元素：每個集合都有一個代表元素，用于標識該集合。集合中的其他元素都可以通過一定的關系與代表元素相連。

基本操作：

初始化：將每個元素都初始化為一個獨立的集合，每個集合的代表元素就是該元素本身。
合并：將兩個不同集合合并為一個集合。通常是將一個集合的代表元素連接到另一個集合的代表元素上，使得兩個集合成為一個更大的集合。
查找：查找某個元素所在集合的代表元素。通過不斷地沿著元素的父指針追溯，最終找到代表元素，從而確定該元素屬于哪個集合。

并查集通常使用數組來實現，數組的下標表示元素，數組中存儲的是該元素的父元素或代表元素的下標。在一些復雜的應用場景中，為了提高并查集的操作效率，還會采用路徑壓縮和按秩合并等優化策略。

并查集在圖論、數據分類、連通性問題等領域有廣泛的應用。例如，在處理圖的連通分量問題時，可以使用并查集來快速判斷兩個頂點是否屬于同一個連通分量，以及合并不同的連通分量。

秩是什么

定義：秩可以看作是樹的高度的一個估計值。在并查集的初始化階段，每個元素都自成一個集合，此時集合的秩通常被初始化為 1，表示單個元素構成的樹高度為 1。

作用：在合并兩個集合時，通過比較兩個集合的秩來決定如何合并，以盡量保持樹的平衡性，避免出現退化的樹結構（即高度過高的樹，會導致查找操作的時間復雜度增加）。

按秩合并策略：

當合并兩個集合時，比較它們的秩。如果兩個集合的秩不同，將秩較小的集合合并到秩較大的集合中。這樣做的原因是，將較小的樹連接到較大的樹上，對整體樹的高度影響較小，有助于保持樹的平衡性。例如，一個秩為 2 的樹和一個秩為 3 的樹合并，會將秩為 2 的樹連接到秩為 3 的樹下面，合并后新樹的秩不變，仍為 3。
如果兩個集合的秩相同，那么可以任選一個集合作為合并的目標集合，并將另一個集合合并到該集合中。在這種情況下，合并后新集合的秩會增加 1。例如，兩個秩都為 2 的樹合并，合并后新樹的秩變為 3。

通過使用秩和按秩合并策略，可以有效地降低并查集操作的時間復雜度，使得在大多數情況下，查找和合并操作都能在接近常數時間內完成。

例子——快速入門

假設有一群人，他們之間存在著不同的朋友關系。我們把每個人看作一個節點，朋友關系看作是連接節點的邊，現在需要判斷兩個人是否在同一個朋友圈中，以及統計朋友圈的數量。

初始化：假設有 5 個人，分別用編號 0 - 4 表示。一開始，每個人都屬于自己獨立的朋友圈，即每個節點的父節點都是它自己。可以用一個數組parent來表示，parent[i]表示節點i的父節點，初始化為parent = [0, 1, 2, 3, 4]。
合并朋友圈：
- 已知 0 和 1 是朋友，通過union操作合并他們所在的集合。找到 0 和 1 的根節點，即 0 和 1 本身，將 1 的父節點設置為 0，此時parent = [0, 0, 2, 3, 4]，表示 0 和 1 在同一個朋友圈中。
- 接著，2 和 3 是朋友，進行同樣的合并操作，將 3 的父節點設置為 2，parent = [0, 0, 2, 2, 4]。
- 然后，1 和 3 是朋友，再次合并。先找到 1 的根節點是 0，3 的根節點是 2，將 2 的父節點設置為 0，parent = [0, 0, 0, 0, 4]，此時 0、1、2、3 都在同一個朋友圈中。
查找：
- 要判斷 4 和 3 是否在同一個朋友圈，通過find操作查找 4 的根節點是 4，3 的根節點是 0，根節點不同，所以 4 和 3 不在同一個朋友圈。
- 要判斷 0 和 2 是否在同一個朋友圈，查找 0 和 2 的根節點都是 0，根節點相同，所以 0 和 2 在同一個朋友圈。
統計朋友圈數量：最后，通過遍歷parent數組，統計根節點的數量，即不同的代表元素的數量，就可以得到朋友圈的數量。在這個例子中，有兩個不同的根節點 0 和 4，所以朋友圈數量為 2。

package mainimport "fmt"// UnionFind 定義并查集結構體
type UnionFind struct {parent []int // parent 切片用于存儲每個元素的父節點，初始時每個元素的父節點是其自身// 在合并兩個集合時，通過比較兩個集合的秩來決定如何合并，以盡量保持樹的平衡性，避免出現退化的樹結構（即高度過高的樹，會導致查找操作的時間復雜度增加）。rank  []int // rank 切片用于記錄每個集合的秩（通常是樹的高度）count int   // 朋友圈的數量
}// NewUnionFind 初始化并查集
func NewUnionFind(n int) *UnionFind {parent := make([]int, n)rank := make([]int, n)for i := range parent {parent[i] = irank[i] = 1}return &UnionFind{parent: parent,rank:   rank,count:  n,}
}// Find 查找元素所在集合的代表元素
func (uf *UnionFind) Find(x int) int {// 如果元素x的父節點（parent[x]）不是它自己，就遞歸的查找它（parent[x]元素）的父節點if uf.parent[x] != x {uf.parent[x] = uf.Find(uf.parent[x])}return uf.parent[x]
}// Union 合并兩個元素所在的集合
func (uf *UnionFind) Union(x, y int) {rootX := uf.Find(x)rootY := uf.Find(y)if rootX == rootY {return}if uf.rank[rootX] < uf.rank[rootY] {rootX, rootY = rootY, rootX}uf.parent[rootY] = rootX         // 更改 rootY 的父節點為 rootXuf.rank[rootX] += uf.rank[rootY] // 更改 rootX 的秩uf.count--                       // 朋友圈數量--
}// GetCount 獲取連通分量的數量
func (uf *UnionFind) GetCount() int {return uf.count
}func main() {// 假設有 5 個人n := 5uf := NewUnionFind(n)// 合并操作，模擬朋友關系uf.Union(0, 1)uf.Union(2, 3)uf.Union(1, 3)// 判斷 4 和 3 是否在同一個朋友圈sameCircle1 := uf.Find(4) == uf.Find(3)fmt.Printf("4 和 3 是否在同一個朋友圈: %v\n", sameCircle1)// 判斷 0 和 2 是否在同一個朋友圈sameCircle2 := uf.Find(0) == uf.Find(2)fmt.Printf("0 和 2 是否在同一個朋友圈: %v\n", sameCircle2)// 統計朋友圈的數量circleCount := uf.GetCount()fmt.Printf("朋友圈的數量: %d\n", circleCount)// 4 和 3 是否在同一個朋友圈: false// 0 和 2 是否在同一個朋友圈: true// 朋友圈的數量: 2
}

例題

在并查集的實現中，rank?數組（或類似用于記錄秩的機制）并不是必需的，有些題目里的并查集沒有使用?rank?數組主要有以下原因：

簡化實現：對于一些簡單的問題場景，不需要通過按秩合并來優化并查集的性能，僅使用路徑壓縮就可以滿足時間復雜度要求。此時可以省略?rank?數組，代碼實現會更簡潔。比如在一些數據規模較小或者對時間復雜度要求不高的問題中，單純的路徑壓縮就能讓并查集的操作效率足夠高。

采用其他優化方式：有些并查集的實現可能不使用?rank?數組來記錄秩，而是采用其他方式來優化合并操作。例如，記錄每個集合的大小，在合并時將較小的集合合并到較大的集合中，這種方法也能在一定程度上避免樹結構的退化，提高查找和合并的效率。

使用路徑壓縮，不使用秩合并

// 使用路徑壓縮，不使用秩合并package maintype UnionFind struct {parent []int
}func NewUnionFind(n int) *UnionFind {parent := make([]int, n)for i := range parent {parent[i] = i}return &UnionFind{parent: parent,}
}// Find 查找
func (uf *UnionFind) Find(x int) int {if uf.parent[x] != x {uf.parent[x] = uf.Find(uf.parent[x])}return uf.parent[x]
}// Union 合并
func (uf *UnionFind) Union(x, y int) {rootX := uf.Find(x)rootY := uf.Find(y)uf.parent[rootY] = rootX
}// IsConnected 判斷兩個元素是否在同一個集合中
func (uf *UnionFind) IsConnected(x, y int) bool {return uf.Find(x) == uf.Find(y)
}

相應的例題：

力扣：547. 省份數量（并查集，也可以用dfs、bfs）

力扣：684. 冗余連接（并查集）

使用路徑壓縮和秩合并

// 使用路徑壓縮和秩合并（優化并查集的性能）package main// UnionFind 定義并查集結構體
type UnionFind struct {parent []intrank   []int
}// NewUnionFind 初始化并查集
func NewUnionFind(n int) *UnionFind {parent := make([]int, n)rank := make([]int, n)for i := range parent {parent[i] = irank[i] = 1}return &UnionFind{parent: parent,rank:   rank,}
}// Find 查找元素所在集合的代表元素，使用路徑壓縮
func (uf *UnionFind) Find(x int) int {if uf.parent[x] != x {uf.parent[x] = uf.Find(uf.parent[x])}return uf.parent[x]
}// Union 合并兩個元素所在的集合，使用按秩合并
func (uf *UnionFind) Union(x, y int) {rootX := uf.Find(x)rootY := uf.Find(y)if rootX == rootY {return}if uf.rank[rootX] < uf.rank[rootY] {rootX, rootY = rootY, rootX}uf.parent[rootY] = rootXuf.rank[rootX] += uf.rank[rootY]
}// IsConnected 判斷兩個元素是否在同一個集合中
func (uf *UnionFind) IsConnected(x, y int) bool {return uf.Find(x) == uf.Find(y)
}

相應的例題：

力扣：1584. 連接所有點的最小費用（Kruskal算法、最小生成樹、并查集）