<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                # 并查集 # 并查集 關于并查集的題目不少,官方給的數據是 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">``` <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find</span><span class="hljs-params">(self, x)</span>:</span> <span class="hljs-keyword">while</span> x != self.parent[x]: x = self.parent[x] <span class="hljs-keyword">return</span> x ``` ``` ### connected ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">connected</span><span class="hljs-params">(self, p, q)</span>:</span> <span class="hljs-keyword">return</span> self.find(p) == self.find(q) ``` ``` ### union ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">union</span><span class="hljs-params">(self, p, q)</span>:</span> <span class="hljs-keyword">if</span> self.connected(p, q): <span class="hljs-keyword">return</span> self.parent[self.find(p)] = self.find(q) ``` ``` ## 完整代碼模板 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">UF</span>:</span> parent = {} cnt = <span class="hljs-params">0</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, M)</span>:</span> <span class="hljs-title"># 初始化 parent 和 cnt</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find</span><span class="hljs-params">(self, x)</span>:</span> <span class="hljs-keyword">while</span> x != self.parent[x]: x = self.parent[x] <span class="hljs-keyword">return</span> x <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">union</span><span class="hljs-params">(self, p, q)</span>:</span> <span class="hljs-keyword">if</span> self.connected(p, q): <span class="hljs-keyword">return</span> self.parent[self.find(p)] = self.find(q) self.cnt -= <span class="hljs-params">1</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">connected</span><span class="hljs-params">(self, p, q)</span>:</span> <span class="hljs-keyword">return</span> self.find(p) == self.find(q) ``` ``` ## 帶路徑壓縮的代碼模板 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">UF</span>:</span> parent = {} size = {} cnt = <span class="hljs-params">0</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, M)</span>:</span> <span class="hljs-title"># 初始化 parent,size 和 cnt</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find</span><span class="hljs-params">(self, x)</span>:</span> <span class="hljs-keyword">while</span> x != self.parent[x]: x = self.parent[x] <span class="hljs-title"># 路徑壓縮</span> self.parent[x] = self.parent[self.parent[x]]; <span class="hljs-keyword">return</span> x <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">union</span><span class="hljs-params">(self, p, q)</span>:</span> <span class="hljs-keyword">if</span> self.connected(p, q): <span class="hljs-keyword">return</span> <span class="hljs-title"># 小的樹掛到大的樹上, 使樹盡量平衡</span> leader_p = self.find(p) leader_q = self.find(q) <span class="hljs-keyword">if</span> self.size[leader_p] < self.size[leader_q]: self.parent[leader_p] = leader_q self.size[leader_p] += self.size[leader_q] <span class="hljs-keyword">else</span>: self.parent[leader_q] = leader_p self.size[leader_q] += self.size[leader_p] self.cnt -= <span class="hljs-params">1</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">connected</span><span class="hljs-params">(self, p, q)</span>:</span> <span class="hljs-keyword">return</span> self.find(p) == self.find(q) ``` ``` 上面是遞歸的方式進行路徑壓縮,寫起來比較簡單。但是有棧溢出的風險。 接下來我們看下迭代的寫法: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">UF</span>:</span> parent = {} <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, equations)</span>:</span> <span class="hljs-title"># 做一些初始化操作</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find</span><span class="hljs-params">(self, x)</span>:</span> <span class="hljs-title"># 根節點</span> r = x <span class="hljs-keyword">while</span> r != parent[r]: r = parent[r] k = x <span class="hljs-keyword">while</span> k != r: <span class="hljs-title"># 暫存parent[k]的父節點</span> j = parent[k] parent[k] = r k = j <span class="hljs-keyword">return</span> r <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">union</span><span class="hljs-params">(self, p, q)</span>:</span> <span class="hljs-keyword">if</span> self.connected(p, q): <span class="hljs-keyword">return</span> self.parent[self.find(p)] = self.find(q) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">connected</span><span class="hljs-params">(self, p, q)</span>:</span> <span class="hljs-keyword">return</span> self.find(p) == self.find(q) ``` ```
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看