一、基本概念和定義

參考文章
并查集（Union-find Sets）是一種非常精巧而實(shí)用的數(shù)據(jù)結(jié)構(gòu)，它主要用于處理一些不相交集合的合并問題。一些常見的用途有求連通子圖、求最小生成樹的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等。
使用并查集時(shí)，首先會(huì)存在一組不相交的動(dòng)態(tài)集合 ，一般都會(huì)使用一個(gè)整數(shù)表示集合中的一個(gè)元素。每個(gè)集合可能包含一個(gè)或多個(gè)元素，并選出集合中的某個(gè)元素作為代表。每個(gè)集合中具體包含了哪些元素是不關(guān)心的，具體選擇哪個(gè)元素作為代表一般也是不關(guān)心的。我們關(guān)心的是，對于給定的元素，可以很快的找到這個(gè)元素所在的集合（的代表），以及合并兩個(gè)元素所在的集合，而且這些操作的時(shí)間復(fù)雜度都是常數(shù)級的。

并查集的基本操作有三個(gè)：
init()：初始化一個(gè)新的并查集，其中包含 s 個(gè)單元素集合。
merge(x, y)：把元素 x 和元素 y 所在的集合合并，要求 x 和 y 所在的集合不相交，如果相交則不合并。
find(x)：找到元素 x 所在的集合的代表，該操作也可以用于判斷兩個(gè)元素是否位于同一個(gè)集合，只要將它們各自的代表比較一下就可以了。

二、原理解釋

相信大家每次在搜索資料查詢并查集的時(shí)候總是鄒巴巴的文字，甚至連圖片都沒有。下面，掀起江湖的腥風(fēng)血雨來趣味解釋并查集的原理。

話說江湖上散落著各式各樣的大俠，有上千個(gè)之多。他們沒有什么正當(dāng)職業(yè)，整天背著劍在外面走來走去，碰到和自己不是一路人的，就免不了要打一架。但大俠們有一個(gè)優(yōu)點(diǎn)就是講義氣，絕對不打自己的朋友。而且他們信奉“朋友的朋友就是我的朋友”，只要是能通過朋友關(guān)系串聯(lián)起來的，不管拐了多少個(gè)彎，都認(rèn)為是自己人。這樣一來，江湖上就形成了一個(gè)一個(gè)的群落，通過兩兩之間的朋友關(guān)系串聯(lián)起來。而不在同一個(gè)群落的人，無論如何都無法通過朋友關(guān)系連起來，于是就可以放心往死了打。但是兩個(gè)原本互不相識(shí)的人，如何判斷是否屬于一個(gè)朋友圈呢？我們可以在每個(gè)朋友圈內(nèi)推舉出一個(gè)比較有名望的人，作為該圈子的代表人物，這樣，每個(gè)圈子就可以這樣命名“齊達(dá)內(nèi)朋友之隊(duì)”“羅納爾多朋友之隊(duì)”……兩人只要互相對一下自己的隊(duì)長是不是同一個(gè)人，就可以確定敵友關(guān)系了。
但是還有問題啊，大俠們只知道自己直接的朋友是誰，很多人壓根就不認(rèn)識(shí)隊(duì)長，要判斷自己的隊(duì)長是誰，只能漫無目的的通過朋友的朋友關(guān)系問下去：“你是不是隊(duì)長？你是不是隊(duì)長？”這樣一來，隊(duì)長面子上掛不住了，而且效率太低，還有可能陷入無限循環(huán)中。于是隊(duì)長下令，重新組隊(duì)。隊(duì)內(nèi)所有人實(shí)行分等級制度，形成樹狀結(jié)構(gòu)，我隊(duì)長就是根節(jié)點(diǎn)，下面分別是二級隊(duì)員、三級隊(duì)員。每個(gè)人只要記住自己的上級是誰就行了。遇到判斷敵友的時(shí)候，只要一層層向上問，直到最高層，就可以在短時(shí)間內(nèi)確定隊(duì)長是誰了。由于我們關(guān)心的只是兩個(gè)人之間是否連通，至于他們是如何連通的，以及每個(gè)圈子內(nèi)部的結(jié)構(gòu)是怎樣的，甚至隊(duì)長是誰，并不重要。所以我們可以放任隊(duì)長隨意重新組隊(duì)，只要不搞錯(cuò)敵友關(guān)系就好了。于是，門派產(chǎn)生了。

下面我們來看并查集的實(shí)現(xiàn)。
各個(gè)門派掌門在成立各派之前，還是孤家寡人的時(shí)候，每個(gè)元素都是一個(gè)單元素集合，即父節(jié)點(diǎn)是其自身：
int pre[1000];
這個(gè)數(shù)組，記錄了每個(gè)大俠的上級是誰。大俠們從1或者0開始編號（依據(jù)題意而定），pre[15]=3就表示15號大俠的上級是3號大俠。如果一個(gè)人的上級就是他自己，那說明他就是掌門人了，查找到此為止。也有孤家寡人自成一派的，比如歐陽鋒，那么他的上級就是他自己。每個(gè)人都只認(rèn)自己的上級。比如胡青牛同學(xué)只知道自己的上級是楊左使。張無忌是誰？不認(rèn)識(shí)！要想知道自己的掌門是誰，只能一級級查上去。

void init(){
    //for(int i=0;i<size;i++) pre[i]=i;   //父節(jié)點(diǎn)是其本身
    for(int i=0;i<size;i++) pre[i]=-1; 
    //這里用到了一個(gè)小技巧，即：掌門人的父結(jié)點(diǎn)是一個(gè)負(fù)數(shù)，且這個(gè)負(fù)數(shù)的絕對值表示的是當(dāng)前門派人數(shù)；
}

接下來，就是 find 操作了，find這個(gè)函數(shù)就是找掌門用的.

int find(int x){
    // return pre[x] == x ? x : find(pre[x]);
    return pre[x] < 0 ? x : find(pre[x]);
}

如果每次都沿著父節(jié)點(diǎn)向上查找，那時(shí)間復(fù)雜度就是樹的高度，完全不可能達(dá)到常數(shù)級。這里需要應(yīng)用一種非常簡單而有效的策略——路徑壓縮。
再來看看路徑壓縮算法。建立門派的過程是用join函數(shù)兩個(gè)人兩個(gè)人地連接起來的，誰當(dāng)誰的手下完全隨機(jī)。最后的樹狀結(jié)構(gòu)會(huì)變成什么樣，我也完全無法預(yù)計(jì)，一字長蛇陣也有可能。這樣查找的效率就會(huì)比較低下。最理想的情況就是所有人的直接上級都是掌門，一共就兩級結(jié)構(gòu)，只要找一次就找到掌門了。哪怕不能完全做到，也最好盡量接近。這樣就產(chǎn)生了路徑壓縮算法。
設(shè)想這樣一個(gè)場景：兩個(gè)互不相識(shí)的大俠碰面了，想知道能不能揍。
于是趕緊打電話問自己的上級：“你是不是掌門？”
上級說：“我不是呀，我的上級是誰誰誰，你問問他看看?！?br> 一路問下去，原來兩人的最終boss都是東廠曹公公。
“ 哎呀呀，原來是自己，西禮西禮，在下三營六組白面葫蘆娃!”
“幸會(huì)幸會(huì)，在下九營十八組仙子狗尾巴花！”
兩人高高興興地手拉手喝酒去了。
“等等等等，兩位同學(xué)請留步，還有事情沒完成呢！”我叫住他倆。
“哦，對了，還要做路徑壓縮。”兩人醒悟。
白面葫蘆娃打電話給他的上級六組長：“組長啊，我查過了，其習(xí)偶們的掌門是曹公公。不如偶們一起及接拜在曹公公手下吧，省得級別太低，以后查找掌門麻環(huán)?！?br> “唔，有道理。”
白面葫蘆娃接著打電話給剛才拜訪過的三營長……仙子狗尾巴花也做了同樣的事情。
這樣，查詢中所有涉及到的人物都聚集在曹公公的直接領(lǐng)導(dǎo)下。每次查詢都做了優(yōu)化處理，所以整個(gè)門派樹的層數(shù)都會(huì)維持在比較低的水平上。路徑壓縮的代碼所實(shí)現(xiàn)的功能就是這么個(gè)意思。

int find(int x, vector<int> &pre) {  //有路徑壓縮版
    int p=x, q;
    while(pre[p]>=0) p = pre[p];

    while(x!=p){
        q = pre[x];
        pre[x] = p;
        x = q;
    }
    return x;
}

再來看看merge函數(shù)，就是在兩個(gè)點(diǎn)之間連一條線，這樣一來，原先它們所在的兩個(gè)板塊的所有點(diǎn)就都可以互通了。這在圖上很好辦，畫條線就行了。但我們現(xiàn)在是用并查集來描述武林中的狀況的，一共只有一個(gè)pre[]數(shù)組，該如何實(shí)現(xiàn)呢？
還是舉江湖的例子，假設(shè)現(xiàn)在武林中的形勢如圖所示。虛竹小和尚與周芷若MM是我非常喜歡的兩個(gè)人物，他們的終極boss分別是玄慈方丈和滅絕師太，那明顯就是兩個(gè)陣營了。我不希望他們互相打架，就對他倆說：“你們兩位拉拉勾，做好朋友吧?！彼麄兛丛谖业拿孀由希饬?。這一同意可非同小可，整個(gè)少林和峨眉派的人就不能打架了。這么重大的變化，可如何實(shí)現(xiàn)呀，要改動(dòng)多少地方？其實(shí)非常簡單，我對玄慈方丈說：“大師，麻煩你把你的上級改為滅絕師太吧。這樣一來，兩派原先的所有人員的終極boss都是師太，那還打個(gè)球?。》凑覀冴P(guān)心的只是連通性，門派內(nèi)部的結(jié)構(gòu)不要緊的?！毙纫宦牽隙ɑ鸫罅耍骸拔铱?，憑什么是我變成她手下呀，怎么不反過來？我抗議！”抗議無效，上天安排的，最大。反正誰加入誰效果是一樣的，我就隨手指定了一個(gè)。

void merge(int x, int y)//虛竹和周芷若做朋友 
{
    int fx = find(x), fy = find(y); //一個(gè)老大是玄慈，一個(gè)是滅絕師太
    if (fx != fy)//不是同一個(gè)人
    {
        pre[fy] += pre[fx];//歸順以后原先是兩個(gè)門派的成員變?yōu)橐粋€(gè)門派，人數(shù)自然是兩個(gè)門派之和
        pre[fx] = fy;//方丈很委屈的做了滅絕的小弟 //選定一個(gè)原則，如果是靠左原則，則將所有左邊的歸順右邊，反之亦然。
    }
}

## 三、算法模板

貼一個(gè)完整代碼：這個(gè)程序用于統(tǒng)計(jì)n個(gè)人，m個(gè)兩兩關(guān)系的門派的個(gè)數(shù)以及每一個(gè)門派的人員數(shù)量。

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

//int find(int x, vector<int> &pre) {  //無路徑壓縮版
//  while(pre[x]>=0) x=pre[x];
//  return x;
//}

int find(int x, vector<int> &pre) {  //有路徑壓縮版
    int p=x, q;
    while(pre[p]>=0) p = pre[p];

    while(x!=p){
        q = pre[x];
        pre[x] = p;
        x = q;
    }
    return x;
}

void merge(int x, int y, vector<int> &pre) {   //虛竹和周芷若做朋友
    int fx = find(x, pre);
    int fy = find(y, pre);//一個(gè)老大是玄慈，一個(gè)是滅絕師太
    if (fx != fy){          //不是同一個(gè)人
        pre[fy] += pre[fx];
        pre[fx] = fy;//方丈很委屈的做了滅絕的小弟 ,靠右原則；
    }
}

int main(){
    int n, m;  //n個(gè)人，m個(gè)兩兩團(tuán)伙，團(tuán)伙之間存在傳遞性，即A<->B,B<->C那么A.B.C均是同一門派。
    cin >> n >> m;
    int ans=0;
    vector<int> pre(n+1, -1);
    for(int i = 0; i<m; i++){
        int x, y;
        cin >> x >> y;
        merge(x, y, pre);
    }

    for (int i = 1; i<=n; i++){
        if (pre[i]<0){
            ans++;
            cout << -pre[i] << endl;  //輸出每一門派的人員數(shù)量
        }
    }

    for(auto n:pre)
        cout<< n << " ";
    return 0;
}
/*
6 5
1 3
2 4
2 5
3 6
1 2
*/

四、做幾個(gè)題檢查一下

1.leetcode547-朋友圈

題目描述

班上有 N 名學(xué)生。其中有些人是朋友，有些則不是。他們的友誼具有是傳遞性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我們可以認(rèn)為 A 也是 C 的朋友。所謂的朋友圈，是指所有朋友的集合。給定一個(gè) N * N 的矩陣 M，表示班級中學(xué)生之間的朋友關(guān)系。如果M[i][j] = 1，表示已知第 i 個(gè)和 j 個(gè)學(xué)生互為朋友關(guān)系，否則為不知道。你必須輸出所有學(xué)生中的已知的朋友圈總數(shù)。

示例 :
輸入:
[[1,1,0],
[1,1,0],
[0,0,1]]
輸出: 2
說明：已知學(xué)生0和學(xué)生1互為朋友，他們在一個(gè)朋友圈。
第2個(gè)學(xué)生自己在一個(gè)朋友圈。所以返回2。

解題思路

套并查集模板就行,很簡單!

代碼

class Solution {
public:
    int find(int x, vector<int> &pre){
        while(pre[x]>=0) x = pre[x];
        return x;
    }

    void merge(int x, int y, vector<int> &pre){
        int fx=find(x, pre);
        int fy=find(y, pre);
        if(fx!=fy){
            pre[fx] += pre[fy];
            pre[fy] = fx;
        }
    }

    int findCircleNum(vector<vector<int>>& M) {
        vector<int> pre(M.size(), -1);
        for(int i=0;i<M.size();i++){
            for(int j=0;j<M.size();j++){
                if(i!=j && M[i][j]==1) merge(i, j, pre);
            }
        }
        int res=0;
        for(int i=0;i<pre.size(); i++){
            if(pre[i]<0) res++;
        }
        return res;
    }
};

2.leetcode990-等式方程的可滿足性

題目描述

給定一個(gè)由表示變量之間關(guān)系的字符串方程組成的數(shù)組，每個(gè)字符串方程 equations[i] 的長度為 4，并采用兩種不同的形式之一："a==b" 或 "a!=b"。在這里，a 和 b 是小寫字母（不一定不同），表示單字母變量名。只有當(dāng)可以將整數(shù)分配給變量名，以便滿足所有給定的方程時(shí)才返回 true，否則返回 false。

示例 ：
輸入：["a==b","b!=a"]
輸出：false
解釋：如果我們指定，a = 1 且 b = 1，那么可以滿足第一個(gè)方程，但無法滿足第二個(gè)方程。沒有辦法分配變量同時(shí)滿足這兩個(gè)方程。

解題思路

套并查集模板就可以,需要注意的是先把所有相等的字符聯(lián)通,然后再處理不等式,檢查是否出現(xiàn)矛盾.

代碼

class Solution {
public:
    int find(int x, vector<int> &pre){
        while(pre[x]>=0) x = pre[x];
        return x;
    }

    void merge(int x, int y, vector<int> &pre){
        int fx = find(x, pre);
        int fy = find(y, pre);
        if(fx!=fy){
            pre[fx] += pre[fy];
            pre[fy] = fx;
        }
    }

    bool equationsPossible(vector<string>& equations) {
        vector<int> pre(26, -1);
        for(int i=0;i<equations.size();i++){
            if(equations[i][1]=='=') merge(equations[i][0]-'a', equations[i][3]-'a', pre);
        }
        for(int i=0;i<equations.size();i++){
            if(equations[i][1]=='!'){
                int fx = find(equations[i][0]-'a', pre);
                int fy = find(equations[i][3]-'a', pre);
                if(fx==fy) return false;
            }
        }
        return true;
    }
};

3.leetcode130-被圍繞的區(qū)域

題目描述

給定一個(gè)二維的矩陣，包含 'X' 和 'O'（字母 O）。找到所有被 'X' 圍繞的區(qū)域，并將這些區(qū)域里所有的 'O' 用 'X' 填充。

示例:
X X X X
X O O X
X X O X
X O X X
運(yùn)行你的函數(shù)后，矩陣變?yōu)椋?br> X X X X
X X X X
X X X X
X O X X
解釋:被圍繞的區(qū)間不會(huì)存在于邊界上，換句話說，任何邊界上的 'O' 都不會(huì)被填充為 'X'。 任何不在邊界上，或不與邊界上的 'O' 相連的 'O' 最終都會(huì)被填充為 'X'。如果兩個(gè)元素在水平或垂直方向相鄰，則稱它們是“相連”的。

解題思路一(并查集)

我們的思路是把所有邊界上的 O看做一個(gè)連通區(qū)域。遇到 O 就執(zhí)行并查集合并操作，這樣所有的 O就會(huì)被分成兩類

• 和邊界上的 O 在一個(gè)連通區(qū)域內(nèi)的。這些 O 我們保留。
• 不和邊界上的 O 在一個(gè)連通區(qū)域內(nèi)的。這些 O就是被包圍的，替換。
  由于并查集我們一般用一維數(shù)組來記錄，方便查找 parants，所以我們將二維坐標(biāo)用 node 函數(shù)轉(zhuǎn)化為一維坐標(biāo)。
  但是有一個(gè)樣例過不了,哭了.百思不得其解,心好累!

代碼

class Solution {
public:
    int find(int x, vector<int> &pre){
        while(pre[x]>=0) x=pre[x];
        return x;
    }

    void merge(int x, int y, vector<int> &pre){
        int fx=find(x, pre);
        int fy=find(y, pre);
        if(fx!=fy){
            pre[fx] += pre[fy];
            pre[fy] = fx;
        }
    }

    void solve(vector<vector<char>>& board) {
        int m=board.size();
        if(m<=0) return ;
        int n=board[0].size();

        vector<int> pre(m*n+1, -1);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='O'){
                    if(i==0||i==m-1||j==0||j==n-1) merge(i*n+j, m*n, pre);
                    else{
                        if(i>0&&board[i-1][j]=='O') merge((i-1)*n+j, i*n+j, pre);
                        if(i<m-1&&board[i+1][j]=='O') merge((i+1)*n+j, i*n+j, pre);
                        if(j>0&&board[i][j-1]=='O') merge(i*n+j-1, i*n+j, pre);
                        if(j<n-1&&board[i][j+1]=='O') merge(i*n+j+1, i*n+j, pre);
                    }
                }
            }
        }

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(find(i*n+j, pre) == find(m*n, pre)) board[i][j] = 'O';
                else board[i][j] = 'X';
            }
        }
    }
};

解題思路二(DFS+標(biāo)記)

• 邊界出現(xiàn)'O'就深搜，改成標(biāo)記，這里用的是'A'，然后再需要一個(gè)集合去標(biāo)記訪問過的點(diǎn)，避免重復(fù)訪問。
• 最后按標(biāo)記變更矩陣。

代碼

class Solution {
public:
    void dfs(vector<vector<char>>& board, int i, int j){
        if(i>=0&&i<board.size()&&j>=0&&j<board[i].size()){
            if(board[i][j]=='O'){
                board[i][j] = 'A';
                dfs(board, i-1, j);
                dfs(board, i+1, j);
                dfs(board, i, j-1);
                dfs(board, i, j+1);
            }
        }
    }

    void solve(vector<vector<char>>& board) {
        int m=board.size();
        if(m<=0) return ;
        int n=board[0].size();

        for(int i=0;i<m;i++){
            dfs(board, i, 0);
            dfs(board, i, n-1);
        }

        for(int j=0;j<n;j++){
            dfs(board, 0, j);
            dfs(board, m-1, j);
        }

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='A') board[i][j] = 'O';
                else board[i][j] = 'X';
            }
        }
    }
};

4.leetcode839-相似字符串組

題目描述

如果我們交換字符串 X 中的兩個(gè)不同位置的字母，使得它和字符串 Y 相等，那么稱 X 和 Y 兩個(gè)字符串相似。例如，"tars" 和 "rats" 是相似的 (交換 0 與 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不與 "tars"，"rats"，或 "arts" 相似?？傊?，它們通過相似性形成了兩個(gè)關(guān)聯(lián)組：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一組中，即使它們并不相似。形式上，對每個(gè)組而言，要確定一個(gè)單詞在組中，只需要這個(gè)詞和該組中至少一個(gè)單詞相似。我們給出了一個(gè)不包含重復(fù)的字符串列表 A。列表中的每個(gè)字符串都是 A 中其它所有字符串的一個(gè)字母異位詞。請問 A 中有多少個(gè)相似字符串組？

示例：
輸入：["tars","rats","arts","star"]
輸出：2
提示：
A.length <= 2000; A[i].length <= 1000; A.length * A[i].length <= 20000; A 中的所有單詞都只包含小寫字母。A 中的所有單詞都具有相同的長度，且是彼此的字母異位詞。此問題的判斷限制時(shí)間已經(jīng)延長。
備注：字母異位詞[anagram]，一種把某個(gè)字符串的字母的位置（順序）加以改換所形成的新詞。

解題思路

• 兩個(gè)字符串是否相似直接掃一遍看對應(yīng)位置不同的字母個(gè)數(shù)
• 維護(hù)并查集，判斷是否相似，相似添加進(jìn)并查集

代碼

class Solution {
public:
    int find(int x, vector<int> &pre) {  //有路徑壓縮版
        int p=x, q;
        while(pre[p]>=0) p = pre[p];

        while(x!=p){
            q = pre[x];
            pre[x] = p;
            x = q;
        }
        return x;
    }
    
    void merge(int x, int y, vector<int> &pre){
        int fx = find(x, pre);
        int fy = find(y, pre);
        if(fx!=fy){
            pre[fx] += pre[fy];
            pre[fy] = fx;
        }
    }

    bool is_ok(string &a, string &b){
        int cnt = 0;
        for(int i=0; i<a.size(); ++i){
            if(a[i] != b[i]) if(++cnt > 2) return false;
        }
        return true;
    }

    int numSimilarGroups(vector<string>& A) {
        A.erase(unique(A.begin(), A.end()), A.end());
        vector<int> pre(A.size(), -1);
        for(int i=1;i<A.size();i++){
            for(int j=0;j<i;j++){
                if(is_ok(A[i],A[j])) merge(i, j, pre);
            }
        }

        int res=0;
        for(int i=0;i<pre.size();i++){
            if(pre[i]<0) res++;
        }
        return res;
    }
};

5.leetcode721-賬號合并

題目描述

給定一個(gè)列表 accounts，每個(gè)元素 accounts[i] 是一個(gè)字符串列表，其中第一個(gè)元素 accounts[i][0] 是 名稱(name)，其余元素是 emails 表示該帳戶的郵箱地址。現(xiàn)在，我們想合并這些帳戶。如果兩個(gè)帳戶都有一些共同的郵件地址，則兩個(gè)帳戶必定屬于同一個(gè)人。請注意，即使兩個(gè)帳戶具有相同的名稱，它們也可能屬于不同的人，因?yàn)槿藗兛赡芫哂邢嗤拿Q。一個(gè)人最初可以擁有任意數(shù)量的帳戶，但其所有帳戶都具有相同的名稱。合并帳戶后，按以下格式返回帳戶：每個(gè)帳戶的第一個(gè)元素是名稱，其余元素是按順序排列的郵箱地址。accounts 本身可以以任意順序返回。

Input:
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'], ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation: 第一個(gè)和第三個(gè) John 是同一個(gè)人，因?yàn)樗麄冇泄餐碾娮余]件 "johnsmith@mail.com"。 第二個(gè) John 和 Mary 是不同的人，因?yàn)樗麄兊碾娮余]件地址沒有被其他帳戶使用。我們可以以任何順序返回這些列表，例如答案[['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']， ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']]仍然會(huì)被接受。

解題思路

• 并查集的思路,自己寫的時(shí)候遇到很多麻煩,就是郵箱的順序一直不知道怎么寫才好!
  最好參考了大佬的寫法,比較清晰, 唉, 菜是原罪啊! 日常許愿,希望盡快能拿到一個(gè)滿意的offer吧!!!

代碼

class Solution {
public:
    int find(int x, vector<int> &pre) {  //有路徑壓縮版
        int p=x, q;
        while(pre[p]>=0) p = pre[p];

        while(x!=p){
            q = pre[x];
            pre[x] = p;
            x = q;
        }
        return x;
    }

    void merge(int x, int y, vector<int> &pre){
        int fx=find(x, pre);
        int fy=find(y, pre);
        if(fx!=fy){
            pre[fx] += pre[fy];
            pre[fy] = fx;
        }
    }

    vector<vector<string> > accountsMerge(vector<vector<string>>& accounts) {
        vector<vector<string> > reaccounts;
        int n = accounts.size();
        if (!n) return reaccounts;
        vector<int> pre(n, -1);
        map<string,int> m;  //郵箱和行號的映射
        for (int i = 1; i < accounts[0].size(); i++){   //添加第一行郵箱
            m[accounts[0][i]] = 0;  //初始化第一行郵箱的父親行號為0
        }
        //先初始化第一行，然后從第二行開始，判斷是否有重復(fù)，逐行將郵箱往m中添加
        for(int i = 1; i < n;i++){
            for(int j = 1;j < accounts[i].size();j++){
                if(m.find(accounts[i][j]) != m.end()){
                    merge(m[accounts[i][j]],i, pre);  //重復(fù)則合并值為父親行號
                }else{
                    m[accounts[i][j]] = i;//如果不重復(fù)，插入,設(shè)值為該行號
                }
            }
        }//至此找出了郵箱和對應(yīng)行號的關(guān)系，確保了唯一性，接著找出郵箱和人的確定集合
        map<int, vector<string> > man;   //姓名+郵箱的 賬戶集合
        for (auto &it:m){    //遍歷郵箱和行號的 映射集合
            int k = find(it.second, pre);
            if (man.find(k) == man.end()){   //沒有該賬戶時(shí)才新增賬戶
                man[k].push_back(accounts[k][0]);
            }
            man[k].push_back(it.first); //添加郵箱到集合
        }
        for(auto it:man) reaccounts.push_back(it.second);    //添加每個(gè)賬戶
        return reaccounts;
    }
};