并查集 · ttttt

# 并查集 # 并查集關于并查集的題目不少，官方給的數據是 30 道（截止 2020-02-20），但是有一些題目雖然官方沒有貼`并查集`標簽，但是使用并查集來說確非常簡單。這類題目如果掌握模板，那么刷這種題會非常快，并且犯錯的概率會大大降低，這就是模板的好處。我這里總結了幾道并查集的題目： - [547. 朋友圈](547.friend-circles.html) - [721. 賬戶合并](https://leetcode-cn.com/problems/accounts-merge/solution/mo-ban-ti-bing-cha-ji-python3-by-fe-lucifer-3/) - [990. 等式方程的可滿足性](https://github.com/azl397985856/leetcode/issues/304) - [1202. 交換字符串中的元素](https://leetcode-cn.com/problems/smallest-string-with-swaps/) 看完這里的內容，建議拿上面的題目練下手，檢測一下學習成果。 ## 概述并查集是一種樹型的數據結構，用于處理一些不交集（Disjoint Sets）的合并及查詢問題。有一個聯合-查找算法（Union-find Algorithm）定義了兩個用于此數據結構的操作： - Find：確定元素屬于哪一個子集。它可以被用來確定兩個元素是否屬于同一子集。 - Union：將兩個子集合并成同一個集合。由于支持這兩種操作，一個不相交集也常被稱為聯合-查找數據結構（Union-find Data Structure）或合并-查找集合（Merge-find Set）。為了更加精確的定義這些方法，需要定義如何表示集合。一種常用的策略是為每個集合選定一個固定的元素，稱為代表，以表示整個集合。接著，Find(x) 返回 x 所屬集合的代表，而 Union 使用兩個集合的代表作為參數。 ## 形象解釋比如有兩個司令。司令下有若干軍長，軍長下有若干師長。。。我們如何判斷某兩個師長是否屬于同一個司令呢（連通性）？ ![](https://img.kancloud.cn/40/35/4035df402ea3b546048caa29d3f86aa3_604x431.jpg) 很簡單，我們順著師長，往上找，找到司令。如果兩個師長找到的是同一個司令，那么就屬于同一個司令。我們用 parent\[x\] = y 表示 x 的 parent 是 y，通過不斷沿著搜索 parent 搜索找到 root，然后比較 root 是否相同即可得出結論。以上過程涉及了兩個基本操作`find`和`connnected`。并查集除了這兩個基本操作，還有一個是`union`。即將兩個集合合并為同一個。如圖有兩個司令： ![](https://img.kancloud.cn/66/a7/66a7eaece8c1bbc75a550f77a9df6843_1177x525.jpg) 我們將其合并為一個聯通域，最簡單的方式就是直接將其中一個司令指向另外一個即可： ![](https://img.kancloud.cn/d1/5e/d15e36a2ac308c763329a66a36da2b2f_1246x456.jpg) 以上就是三個核心 API `find`，`connnected` 和 `union`，的形象化解釋，下面我們來看下代碼實現。 ## 核心 API ### find ``` <pre class="calibre18">``` def find(self, x): while x != self.parent[x]: x = self.parent[x] return x ``` ``` ### connected ``` <pre class="calibre18">``` def connected(self, p, q): return self.find(p) == self.find(q) ``` ``` ### union ``` <pre class="calibre18">``` def union(self, p, q): if self.connected(p, q): return self.parent[self.find(p)] = self.find(q) ``` ``` ## 完整代碼模板 ``` <pre class="calibre18">``` class UF: parent = {} cnt = 0 def __init__(self, M): # 初始化 parent 和 cnt def find(self, x): while x != self.parent[x]: x = self.parent[x] return x def union(self, p, q): if self.connected(p, q): return self.parent[self.find(p)] = self.find(q) self.cnt -= 1 def connected(self, p, q): return self.find(p) == self.find(q) ``` ``` ## 帶路徑壓縮的代碼模板 ``` <pre class="calibre18">``` class UF: parent = {} size = {} cnt = 0 def __init__(self, M): # 初始化 parent，size 和 cnt def find(self, x): while x != self.parent[x]: x = self.parent[x] # 路徑壓縮 self.parent[x] = self.parent[self.parent[x]]; return x def union(self, p, q): if self.connected(p, q): return # 小的樹掛到大的樹上，使樹盡量平衡 leader_p = self.find(p) leader_q = self.find(q) if self.size[leader_p] < self.size[leader_q]: self.parent[leader_p] = leader_q self.size[leader_p] += self.size[leader_q] else: self.parent[leader_q] = leader_p self.size[leader_q] += self.size[leader_p] self.cnt -= 1 def connected(self, p, q): return self.find(p) == self.find(q) ``` ``` 上面是遞歸的方式進行路徑壓縮，寫起來比較簡單。但是有棧溢出的風險。接下來我們看下迭代的寫法： ``` <pre class="calibre18">``` class UF: parent = {} def __init__(self, equations): # 做一些初始化操作 def find(self, x): # 根節點 r = x while r != parent[r]: r = parent[r] k = x while k != r: # 暫存parent[k]的父節點 j = parent[k] parent[k] = r k = j return r def union(self, p, q): if self.connected(p, q): return self.parent[self.find(p)] = self.find(q) def connected(self, p, q): return self.find(p) == self.find(q) ``` ```