題目來(lái)源知名公司的筆試題目

題目：假如已知有n個(gè)人和m對(duì)好友關(guān)系（存于數(shù)字r）香璃。如果兩個(gè)人是直接或間接的好友（好友的好友的好友...），則認(rèn)為他們屬于同一個(gè)朋友圈舟误，請(qǐng)寫程序求出這n個(gè)人里一共有多少個(gè)朋友圈葡秒。假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}眯牧，表示有5個(gè)人蹋岩，1和2是好友，2和3是好友学少，4和5是好友剪个，則1、2版确、3屬于一個(gè)朋友圈扣囊，4、5屬于另一個(gè)朋友圈绒疗，結(jié)果為2個(gè)朋友圈如暖。

** 解答：**這個(gè)題目屬于數(shù)據(jù)結(jié)構(gòu)中并查集的應(yīng)用，并查集屬于一種高級(jí)數(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) // 初始化并查集忌堂，各點(diǎn)為孤立點(diǎn)盒至，分支數(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 } }));
    }
}

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

運(yùn)行結(jié)果

為了講解并查集士修，來(lái)舉一個(gè)有趣的例子

話說(shuō)江湖上散落著各式各樣的大俠枷遂，有上千個(gè)之多。他們沒有什么正當(dāng)職業(yè)棋嘲，整天背著劍在外面走來(lái)走去酒唉，碰到和自己不是一路人的，就免不了要打一架沸移。但大俠們有一個(gè)優(yōu)點(diǎn)就是講義氣痪伦，絕對(duì)不打自己的朋友。而且他們信奉“朋友的朋友就是我的朋友”雹锣，只要是能通過(guò)朋友關(guān)系串聯(lián)起來(lái)的网沾，不管拐了多少個(gè)彎，都認(rèn)為是自己人蕊爵。這樣一來(lái)辉哥，江湖上就形成了一個(gè)一個(gè)的群落，通過(guò)兩兩之間的朋友關(guān)系串聯(lián)起來(lái)攒射。而不在同一個(gè)群落的人醋旦，無(wú)論如何都無(wú)法通過(guò)朋友關(guān)系連起來(lái)，于是就可以放心往死了打会放。

但是兩個(gè)原本互不相識(shí)的人饲齐，如何判斷是否屬于一個(gè)朋友圈呢？我們可以在每個(gè)朋友圈內(nèi)推舉出一個(gè)比較有名望的人咧最，作為該圈子的代表人物捂人，這樣甩骏，每個(gè)圈子就可以這樣命名“齊達(dá)內(nèi)朋友之隊(duì)”“羅納爾多朋友之隊(duì)”……兩人只要互相對(duì)一下自己的隊(duì)長(zhǎng)是不是同一個(gè)人，就可以確定敵友關(guān)系了先慷。 但是還有問(wèn)題啊，大俠們只知道自己直接的朋友是誰(shuí)咨察，很多人壓根就不認(rèn)識(shí)隊(duì)長(zhǎng)论熙，要判斷自己的隊(duì)長(zhǎng)是誰(shuí)，只能漫無(wú)目的的通過(guò)朋友的朋友關(guān)系問(wèn)下去：“你是不是隊(duì)長(zhǎng)摄狱？你是不是隊(duì)長(zhǎng)脓诡？”這樣一來(lái)，隊(duì)長(zhǎng)面子上掛不住了媒役，而且效率太低祝谚，還有可能陷入無(wú)限循環(huán)中。于是隊(duì)長(zhǎng)下令酣衷，重新組隊(duì)交惯。隊(duì)內(nèi)所有人實(shí)行分等級(jí)制度，形成樹狀結(jié)構(gòu)穿仪，我隊(duì)長(zhǎng)就是根節(jié)點(diǎn)席爽，下面分別是二級(jí)隊(duì)員、三級(jí)隊(duì)員啊片。每個(gè)人只要記住自己的上級(jí)是誰(shuí)就行了只锻。遇到判斷敵友的時(shí)候，只要一層層向上問(wèn)紫谷，直到最高層齐饮，就可以在短時(shí)間內(nèi)確定隊(duì)長(zhǎng)是誰(shuí)了。由于我們關(guān)心的只是兩個(gè)人之間是否連通笤昨，至于他們是如何連通的祖驱，以及每個(gè)圈子內(nèi)部的結(jié)構(gòu)是怎樣的，甚至隊(duì)長(zhǎng)是誰(shuí)瞒窒，并不重要羹膳。所以我們可以放任隊(duì)長(zhǎng)隨意重新組隊(duì)，只要不搞錯(cuò)敵友關(guān)系就好了根竿。于是陵像，門派產(chǎn)生了。

門派關(guān)系圖

下面我們來(lái)看并查集的實(shí)現(xiàn)

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

這個(gè)數(shù)組寇壳，記錄了每個(gè)大俠的上級(jí)是誰(shuí)醒颖。大俠們從1或者0開始編號(hào)（依據(jù)題意而定），set[15]=3就表示15號(hào)大俠的上級(jí)是3號(hào)大俠壳炎。如果一個(gè)人的上級(jí)就是他自己泞歉，那說(shuō)明他就是掌門人了逼侦，查找到此為止。也有孤家寡人自成一派的腰耙，比如歐陽(yáng)鋒榛丢，那么他的上級(jí)就是他自己。每個(gè)人都只認(rèn)自己的上級(jí)挺庞。比如胡青牛同學(xué)只知道自己的上級(jí)是楊左使晰赞。張無(wú)忌是誰(shuí)？不認(rèn)識(shí)选侨！要想知道自己的掌門是誰(shuí)掖鱼，只能一級(jí)級(jí)查上去。
find這個(gè)函數(shù)就是找掌門用的援制，意義再清楚不過(guò)了（路徑壓縮算法先不論戏挡，后面再說(shuō)）。

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

再來(lái)看看join函數(shù)晨仑，就是在兩個(gè)點(diǎn)之間連一條線褐墅，這樣一來(lái)，原先它們所在的兩個(gè)板塊的所有點(diǎn)就都可以互通了洪己。這在圖上很好辦掌栅，畫條線就行了。但我們現(xiàn)在是用并查集來(lái)描述武林中的狀況的码泛，一共只有一個(gè)set[]數(shù)組猾封，該如何實(shí)現(xiàn)呢？

還是舉江湖的例子噪珊，假設(shè)現(xiàn)在武林中的形勢(shì)如圖所示晌缘。虛竹小和尚與周芷若MM是我非常喜歡的兩個(gè)人物，他們的終極boss分別是玄慈方丈和滅絕師太痢站，那明顯就是兩個(gè)陣營(yíng)了磷箕。我不希望他們互相打架，就對(duì)他倆說(shuō)：“你們兩位拉拉勾阵难，做好朋友吧岳枷。”他們看在我的面子上呜叫，同意了空繁。這一同意可非同小可，整個(gè)少林和峨眉派的人就不能打架了朱庆。這么重大的變化盛泡，可如何實(shí)現(xiàn)呀，要改動(dòng)多少地方娱颊？其實(shí)非常簡(jiǎn)單傲诵，我對(duì)玄慈方丈說(shuō)：“大師凯砍，麻煩你把你的上級(jí)改為滅絕師太吧。這樣一來(lái)拴竹，兩派原先的所有人員的終極boss都是師太悟衩，那還打個(gè)球啊栓拜！反正我們關(guān)心的只是連通性座泳，門派內(nèi)部的結(jié)構(gòu)不要緊的×馐簦”玄慈一聽肯定火大了：“我靠，憑什么是我變成她手下呀舰罚，怎么不反過(guò)來(lái)纽门？我抗議！”抗議無(wú)效营罢，上天安排的赏陵，最大。反正誰(shuí)加入誰(shuí)效果是一樣的饲漾，我就隨手指定了一個(gè)蝙搔。所以下面這段函數(shù)的意思很明白了吧？

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

再來(lái)看看路徑壓縮算法吃型。建立門派的過(guò)程是用join函數(shù)兩個(gè)人兩個(gè)人地連接起來(lái)的，誰(shuí)當(dāng)誰(shuí)的手下完全隨機(jī)僚楞。最后的樹狀結(jié)構(gòu)會(huì)變成什么胎唇樣勤晚，其實(shí)完全無(wú)法預(yù)計(jì)，一字長(zhǎng)蛇陣也有可能泉褐。這樣查找的效率就會(huì)比較低下赐写。最理想的情況就是所有人的直接上級(jí)都是掌門，一共就兩級(jí)結(jié)構(gòu)膜赃，只要找一次就找到掌門了挺邀。哪怕不能完全做到，也最好盡量接近跳座。這樣就產(chǎn)生了路徑壓縮算法端铛。
設(shè)想這樣一個(gè)場(chǎng)景：兩個(gè)互不相識(shí)的大俠碰面了，想知道能不能揍疲眷。
于是趕緊打電話問(wèn)自己的上級(jí)：“你是不是掌門沦补？”
上級(jí)說(shuō)：“我不是呀，我的上級(jí)是誰(shuí)誰(shuí)誰(shuí)咪橙，你問(wèn)問(wèn)他看看夕膀⌒榈梗”
一路問(wèn)下去，原來(lái)兩人的最終boss都是東廠曹公公产舞。
“哎呀呀魂奥，原來(lái)是自己人，失禮失禮易猫，在下三營(yíng)六組白面葫蘆娃!”
“幸會(huì)幸會(huì)耻煤，在下九營(yíng)十八組仙子狗尾巴花！”
兩人高高興興地手拉手喝酒去了准颓。
“等等等等哈蝇，兩位同學(xué)請(qǐng)留步，還有事情沒完成呢攘已！”我叫住他倆炮赦。
“哦，對(duì)了样勃，還要做路徑壓縮吠勘。”兩人醒悟峡眶。
白面葫蘆娃打電話給他的上級(jí)六組長(zhǎng)：“組長(zhǎng)啊剧防，我查過(guò)了，其習(xí)偶們的掌門是曹公公辫樱。不如偶們一起及接拜在曹公公手下吧峭拘，省得級(jí)別太低，以后查找掌門麻環(huán)狮暑∨锼簦”
“唔，有道理心例∠瑁”
白面葫蘆娃接著打電話給剛才拜訪過(guò)的三營(yíng)長(zhǎng)……仙子狗尾巴花也做了同樣的事情。
這樣止后，查詢中所有涉及到的人物都聚集在曹公公的直接領(lǐng)導(dǎo)下瞎惫。每次查詢都做了優(yōu)化處理，所以整個(gè)門派樹的層數(shù)都會(huì)維持在比較低的水平上译株。路徑壓縮的代碼瓜喇，看得懂很好，看不懂也沒關(guān)系歉糜，直接抄上用就行了乘寒。

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

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

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í)、上級(jí)的上級(jí)等人匪补，全部人的上級(jí)全部是掌門人
            j = set[i];
            set[i] = r;
            i = j;
        }
        return r;
    }