題目來源知名公司的筆試題目

題目：假如已知有n個人和m對好友關(guān)系（存于數(shù)字r）。如果兩個人是直接或間接的好友（好友的好友的好友...），則認(rèn)為他們屬于同一個朋友圈，請寫程序求出這n個人里一共有多少個朋友圈。假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5個人，1和2是好友，2和3是好友，4和5是好友，則1、2、3屬于一個朋友圈，4、5屬于另一個朋友圈，結(jié)果為2個朋友圈。

** 解答：**這個題目屬于數(shù)據(jù)結(jié)構(gòu)中并查集的應(yīng)用，并查集屬于一種高級數(shù)據(jù)結(jié)構(gòu),這道題目的代碼如下：

public class Test {
    private int[] set = new int[1000];
    public int find(int x) { // 帶路徑優(yōu)化的并查集查找算法
        int i, j, r;
        r = x;
        while (set[r] != r){
            r = set[r];
        }
        i = x;
        while (i != r) {
            j = set[i];
            set[i] = r;
            i = j;
        }
        return r;
    }

    public void join(int x, int y) { // 優(yōu)化的并查集歸并算法
        int t = find(x);
        int h = find(y);
        if (t < h)
            set[h] = t;
        else
            set[t] = h;
    }

    int friends(int n, int m, int[][] r) {
        int i, count;
        for (i = 1; i <= n; ++i) // 初始化并查集，各點為孤立點，分支數(shù)為n
            set[i] = i;
        for (i = 0; i < m; ++i)
            join(r[i][0], r[i][1]);
        count = 0;
        for (i = 1; i <= n; ++i) {
            if (set[i] == i)
                count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(new Test().friends(5, 3, new int[][] { { 1, 2 }, { 2, 3 }, { 4, 5 } }));
    }
}

運行結(jié)果，正確答案為2

運行結(jié)果

為了講解并查集，來舉一個有趣的例子

話說江湖上散落著各式各樣的大俠，有上千個之多。他們沒有什么正當(dāng)職業(yè)，整天背著劍在外面走來走去，碰到和自己不是一路人的，就免不了要打一架。但大俠們有一個優(yōu)點就是講義氣，絕對不打自己的朋友。而且他們信奉“朋友的朋友就是我的朋友”，只要是能通過朋友關(guān)系串聯(lián)起來的，不管拐了多少個彎，都認(rèn)為是自己人。這樣一來，江湖上就形成了一個一個的群落，通過兩兩之間的朋友關(guān)系串聯(lián)起來。而不在同一個群落的人，無論如何都無法通過朋友關(guān)系連起來，于是就可以放心往死了打。

但是兩個原本互不相識的人，如何判斷是否屬于一個朋友圈呢？我們可以在每個朋友圈內(nèi)推舉出一個比較有名望的人，作為該圈子的代表人物，這樣，每個圈子就可以這樣命名“齊達(dá)內(nèi)朋友之隊”“羅納爾多朋友之隊”……兩人只要互相對一下自己的隊長是不是同一個人，就可以確定敵友關(guān)系了。 但是還有問題啊，大俠們只知道自己直接的朋友是誰，很多人壓根就不認(rèn)識隊長，要判斷自己的隊長是誰，只能漫無目的的通過朋友的朋友關(guān)系問下去：“你是不是隊長？你是不是隊長？”這樣一來，隊長面子上掛不住了，而且效率太低，還有可能陷入無限循環(huán)中。于是隊長下令，重新組隊。隊內(nèi)所有人實行分等級制度，形成樹狀結(jié)構(gòu)，我隊長就是根節(jié)點，下面分別是二級隊員、三級隊員。每個人只要記住自己的上級是誰就行了。遇到判斷敵友的時候，只要一層層向上問，直到最高層，就可以在短時間內(nèi)確定隊長是誰了。由于我們關(guān)心的只是兩個人之間是否連通，至于他們是如何連通的，以及每個圈子內(nèi)部的結(jié)構(gòu)是怎樣的，甚至隊長是誰，并不重要。所以我們可以放任隊長隨意重新組隊，只要不搞錯敵友關(guān)系就好了。于是，門派產(chǎn)生了。

門派關(guān)系圖

下面我們來看并查集的實現(xiàn)

private int[] set = new int[1000];

這個數(shù)組，記錄了每個大俠的上級是誰。大俠們從1或者0開始編號（依據(jù)題意而定），set[15]=3就表示15號大俠的上級是3號大俠。如果一個人的上級就是他自己，那說明他就是掌門人了，查找到此為止。也有孤家寡人自成一派的，比如歐陽鋒，那么他的上級就是他自己。每個人都只認(rèn)自己的上級。比如胡青牛同學(xué)只知道自己的上級是楊左使。張無忌是誰？不認(rèn)識！要想知道自己的掌門是誰，只能一級級查上去。
find這個函數(shù)就是找掌門用的，意義再清楚不過了（路徑壓縮算法先不論，后面再說）。

public int find(int x) {
    // 查找根節(jié)點
    int r = x;
    while (set[r] != r) {// 如果我的上級不是我的掌門就不停的查找
        r = set[r];// 從我的上級繼續(xù)往上找
    } // 找到掌門人
    return r;// 返回掌門人
}

再來看看join函數(shù)，就是在兩個點之間連一條線，這樣一來，原先它們所在的兩個板塊的所有點就都可以互通了。這在圖上很好辦，畫條線就行了。但我們現(xiàn)在是用并查集來描述武林中的狀況的，一共只有一個set[]數(shù)組，該如何實現(xiàn)呢？

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

public void join(int x,int y){//讓虛竹和周芷若做朋友
    int fx = find(x);//找到玄慈方丈
    int fy = find(y);//找到滅絕師太
    if(fx!=fy){//玄慈和滅絕顯然不是同一個人
        set[fx] = fy; //尼姑優(yōu)先，方丈委屈只好做老尼姑的手下了
    }
}

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

路徑壓縮后的結(jié)構(gòu)圖

現(xiàn)在來看路徑壓縮代碼：

public int find(int x) { // 帶路徑優(yōu)化的并查集查找算法
        int i, j, r;
        r = x;
        while (set[r] != r){//找到掌門人
            r = set[r];
        }
        i = x;
        while (i != r) {//我的上級、上級的上級等人，全部人的上級全部是掌門人
            j = set[i];
            set[i] = r;
            i = j;
        }
        return r;
    }