能否用通俗易懂的方法解釋下不相交集這種數據結構？

01-05

我最近在看《數據結構與演算法分析（c語言描述）》時看到了不相交集（disjoint set）這種數據結構，由於英語水平有限，對於書中對該數據結構的描述與介紹部分不是很理解，比如這裡的等價到底是什麼意思，好像與一般認識的等價不同啊。求大神幫我理解下改數據結構的內容。
同時還想問一下在學習編程時對於數據結構與演算法分析這本書需要掌握到什麼程度。

等價的定義就是滿足自反性、對稱性、傳遞性三條性質的二元關係，你所說的「一般認識的等價」似乎並沒有經過嚴格的定義，是個模糊的概念.

disjoint set 更常使用的譯名叫並查集，這種數據結構支持合併和查找兩個操作.

合併兩個元素將會使這兩個元素等價，查找可以得到某個元素所在的等價類的代表元.

舉個例子，現在有幾千個新生入學要安排宿舍，合併操作就是將兩個同學安排到同一間宿舍中，而查找操作可以得到某個同學所在宿舍的舍長. 這裡同一個宿舍里的同學就是等價的，因為滿足自反性（自己和自己在同一個宿舍里）、對稱性（如果小紅和小黃在同一個宿舍，那麼小黃和小紅在同一個宿舍）、傳遞性（如果小紅和小黃同宿舍，小黃和小蘭同宿舍，那麼小紅和小蘭同宿舍）三條性質.

具體實現和演算法優化可以上網搜索，參考相關資料.

其實你自己用一堆 map, set 疊在一起也能實現，只是 DisjointSet/UnionFind 內部數據結構更簡單直觀，專門針對大規模的集合：創建，聯合做了針對性的優化，性能比你的 map + set 好很多而已。

某些特定問題確實用 DisjointSet / UnionFind 更好點，比如你想解這題的話：

1099. Work Scheduling @ Timus Online Judge

DisjointSet / UnionFind 可以很好配合 blossom 方法來計算增廣路徑。

基本方法 wiki 上已經講的很清楚了，就是 find/union兩個方法：

find 就是查找節點所在集合的根節點

union 就是合併兩個集合

wiki上的代碼其實還可以有很多優化的方法，比如我們可以寫個更快點的 C++ 版本，把查找和聯合的性能再進一步提高一點：

class CUnionFind { protected: #define MAX 256 int weight[MAX]; int father[MAX]; int temp[MAX * 2];


public:

    inline const int operator [](int vertex) {

        if (father[vertex] == 0) {

            father[vertex] = vertex;

            weight[vertex] = 1;

            return father[vertex];

        }

        int index = 0, i;

        int *path = temp;

        path[index++] = vertex;

        int root = father[vertex];

        while (root != path[index - 1]) {

            path[index++] = root;

            root = father[root];

        }

        i = index - 1;

        for (; i &>= 0; i--, path++) {

            father[path[0]] = root;

        }

        return root;

    }
    inline CUnionFind unions(const int *objs, int size) {

        int m = -2, h = 0, r, w, i, index = 0;
        if (size == 0) return *this;

        int *roots = temp[MAX];

        index = 0;

        for (i = size - 1; i &>= 0; i--) {

            r = this-&>operator[](objs[i]);

            roots[index++] = r;

            if (m &< weight[r]) m = weight[r], h = r;
        }
        int *v = roots[0];
        for (i = index - 1; i &>= 0; i--, v++) {

            if ((w = v[0]) != h) {

                weight[h] += weight[w];

                father[w] = h;

            }

        }

        return *this;

    }

void reset(int size) { memset(weight, 0, sizeof(int) * size); memset(father, 0, sizeof(int) * size); } };

查找就是 operator[]，聯合就是 unions，是吧，就這兩個方法，你 set + map 肯定也能實現，只是這個方法更直接，性能更好。

以前做地圖生成時，需要將屏幕上隨機的節點，連接成一系列「通路」讓它看起來更真實些，

而不是象下面這幅沒有規則任意隨機兩個節點鏈接起來的圖：

頻繁的建立集合，聯合集合，最終把集合歸併成一個成為最終隨機地圖的樣子，在這個過程中，使用 DisjointSet / UnionFind 也很酸爽。當然，離開了特定問題，如果只是平時做 UI/資料庫的話，應該不會碰得到。

不會用到嗎？我記得我用過一次，以前做的某個投票網站當中需要查封小號刷票的作弊賬號，就在後台悄悄做了一個設置，如果某個人不小心帶著相同的cookies登錄了不同的賬號（也就是在同一個瀏覽器上退出一個賬號之後又登入了另一個賬號），登錄系統就會悄悄標記這兩個賬號屬於同一個人，如果A和B是同一個人，B和C也是同一個人，那麼A、B、C都是同一個人，我們最後只關心哪些賬號是同一個人而哪些不是，並不關心究竟是通過怎樣的步驟發現它們是同一個人的，這就是並查集最典型的應用。這個問題就可以在MySQL裡面創建一個表，它有兩個欄位，第一個叫做ID，主鍵，第二個叫做Parent，當前等價的父節點，這就是一個MySQL數據表表示的並查集，然後隨便用SELECT和UPDATE實現一下，並查集接近O(1)的複雜度，一般也就幾次MySQL查詢，No problem！

不相交集數據結構和不相交集合森林（Disjoint Set Forest）是兩個層面的概念，後者是前者的一種高效實現。

一個不相交集數據結構用來表示對元素的分類，分類之間彼此不相交。任意兩個元素是否同類可以描述為一個等價關係。

而這個結構要求可以做到這種事情：

查詢某個元素被分到了哪個類
合併兩個類

如果使用常規的 Map/Hashtable 處理不相交集，對問題 1 很容易解決，但是對於問題 2，需要 O(n) 時間才能完成合併；不相交集合森林把兩個問題的解決時間都幾乎做到了 O(1)，因此成為了最常用的不相交集數據結構。

謝邀。

第一個問題，不相交集應該就是個並查集吧，並查集這個名字比較常用，這方面的資料也很多，自己再看看吧。

第二個問題，太大，不會回答。

你所說的一般認識的等價是不是下面這個定義？

設有兩個命題p和q,如果由p作為條件能使得結論q成立，則稱p是q的充分條件；若由q能使p成立則稱p是q的必要條件；如果p與q能互推（即無論是由q推出p還是p推出q都成立），則稱p是q的充分必要條件，簡稱充要條件，也稱p與q等價。

你仔細看一下8.1節的標題：Equivalence Relations，翻譯過來，叫等價關係。

上面的定義中，這個等價，局限於對命題之間的關係的討論。

但是，我們要考慮關聯的東西並不只是命題，

比如，人，我們要考慮，朋友關係，居住在一起，等等的聯繫。

不相交集(*)適用於描述用是否滿足等價關係來劃分的等價類。

(*)：國內更多使用 並查集 這個中文名詞，主要還是國內的大多數人先碰到這個詞，這個稱呼還直接說明了這種數據結構的2種最基本操作，所以，下文均稱並查集。另，在英文網站上，dsu也會用於指代不相交集，是disjoint set union的縮寫

等價關係是什麼？

定語是等價，主體是關係。所以，等價關係，首先是關係。

怎麼樣的關係算等價關係？你的書上給了3個數學公式來說明其3個條件：自反性、對稱性、傳遞性。

下面邊舉例子邊說明。

自反性是說，這個關係必須自己對自己有效。

比如A記得B。一般人總會自己記得自己。但是如果發生事故了，失憶了，自己記不得自己是誰了（好狗血的劇情）……所以，記得這個關係不見得滿足自反性。

對稱性是說，A向B有這種關係，B向A必須也有這種關係。

比如上面提到的，命題的等價，A能推導出B，B必須能推導出A，才能說A和B這兩個命題是等價的，這就直接體現出了對稱性的要求。

再比如QQ好友的關係。A是B的QQ好友，但是這不一定是雙向好友關係，完全可以就B加了A為QQ好友，A不加B為QQ好友，成了個單向關係，這就不滿足對稱性要求。

傳遞性是說，如果A和B之間有關係R，B和C之間有關係R，A和C之間也必須有這種關係R。

比如現在3個命題，A、B、C，我們現在證明了A和B等價，B和C等價，那麼A和C之間也是等價的。因為，我們可以用證明A到B到C的辦法來證明A可以推導出C，反過來操作，可以證明出C可以推導出A，這就證明了A和C也等價。當然你可以隨便加入一個命題並推出和某個命題X等價，那與X等價的其他命題可以以一樣的操作證明出與新命題等價。

所以，命題之間的等價，這是一種等價關係。

再考慮，加強一下QQ好友關係：必須是雙向好友，不允許單向好友的存在。

但是這仍然不是等價關係：我們不能說A和B互為好友，B和C互為好友，A和C就一定互為好友了。

==========================分割線==========================

然而，花這麼多時間，解釋了等價關係，對理解並查集，

一點用都沒有。

（因為，為了快速理解並查集做了什麼，完全不需要這些鋪墊，直接舉一個運用並查集的例子，就行了，只是因為你問了，還有沿著課本的邏輯思路（這樣思路是很嚴密），才在這裡詳細解釋。）

我們來看看並查集能幹什麼。

比如，我們現在要維護一下，學生和學院之間的從屬關係。

假設只會有查學生屬於哪個學院的查詢請求。

比如我們說，小張、小李屬於軟體工程學院，小王屬於計算機學院。

那好像很簡單啊，你建立了一張表：

學生學院

小張軟體工程學院

小李軟體工程學院

小王計算機學院

然後學校來了一批新生：A進軟體工程學院，B、C、D進計算機學院，你需要把他們插入進去

學生學院

小張軟體工程學院

小李軟體工程學院

小王計算機學院

小A 軟體工程學院

小B 計算機學院

小C 計算機學院

小D 計算機學院

到此都很簡單。

然後，校領導突然說：我們要把軟體工程學院合併到計算機學院！

怎麼辦？

現在7個人，你暴力修改還好說。

人數不多，或者合併次數少，還好說。

如果我現在人數有~10萬，有~5萬次的合併要求，更多的查詢要求呢？

下班再更……

並查集顧名思義就是集合的合併（Union）和查詢(Find)兩種操作。

Find過程：阿里和騰訊合併前，你隨便問一個工程師，要是他們的leader→leader的leader……最後是馬雲，那他們是阿里的，查詢之後將該工程師及其所有上級的leader修改為馬雲（路徑壓縮）；要是他們的leader→leader的leader……最後是小馬哥，那他們是騰訊的，查詢之後將該工程師及其所有上級的leader修改為小馬哥（路徑壓縮）。

Union過程：倆工程師分別是阿里和騰訊的，要求合併兩家公司，然後倆人分別詢問自己的leader……leader的leader……最後問到馬雲，這個過程中將該工程師及其所有上級的leader修改為馬雲（路徑壓縮），另外一個同樣問到了小馬哥。

一比較，馬雲更有錢，所以馬雲收了小馬哥（rank機制）。

我的博客：【演算法導論-36】並查集(Disjoint Set)詳解

一看就會，看這裡

http://algs4.cs.princeton.edu/15uf/

還有各種優化方式

完整代碼在這裡面Fundamentals

ppt看這裡 http://algs4.cs.princeton.edu/lectures/15UnionFind.pdf

ps: 剛剛看了下這個課程今天開課 https://www.coursera.org/learn/introduction-to-algorithms/home/week/1 這裡裡面剛好有 Union-Find

實際代碼OpenCV中有Clustering

C語言的看英文的了

這個，我服

本身還是很明白的，複雜度證明有點麻煩。建議看這本，藏在了角落裡（5.1.4節）。

並查集是很基本的數據結構，找個中文博客應該能讓你快速掌握。

對於演算法和數據結構的掌握程度，主要看你目標吧，如果目標是開發，那麼隨便看看就得了；如果想做得高級點，比如一些應用方面的創新（數據挖據、機器學習、圖形學、資料庫……），可能就得多學一點；如果再高級點，比如理論層面的工作（計算理論、量子計算、資訊理論……）可能要把主要精力放在數學上。

A,B,C,D四個人組成2個集合（A,B），（C,D），用A來表示第一個集合的老大，用C來表示第二個集合的老大，也就是（A,B的老大是A，C，D的老大是C），這樣你就很容易知道每個個人的老大是誰了，然後這兩個集合合體了，你把C的老大標記成A，這時候你想找D的老大是誰的時候，可以這樣子：D標記的老大是C，C的老大是A，然後就知道D的老大也是A了，這時候順便把D的標記改成A，這樣子下次找的話局不需要C了