題目

題目背景

若某個(gè)家族人員過(guò)于龐大，要判斷兩個(gè)是否是親戚，確實(shí)還很不容易，現(xiàn)在給出某個(gè)親戚關(guān)系圖，求任意給出的兩個(gè)人是否具有親戚關(guān)系。

思路

對(duì)于該題而言，考察的是并查集，也就是小怪獸逐個(gè)找上級(jí)領(lǐng)導(dǎo)的思路，指導(dǎo)找到最終的Boss停止下來(lái)，如果兩個(gè)怪獸要打架，需要問(wèn)一問(wèn)他們的上級(jí)領(lǐng)導(dǎo)，領(lǐng)導(dǎo)再問(wèn)領(lǐng)導(dǎo)，逐級(jí)向上，最終發(fā)現(xiàn)它們屬于同一個(gè)Boss的部署的話就不能再打架了，這道題同樣的思路，如果斗羅大陸的一開始白沉香不知道唐三是親戚的話，他們就會(huì)先詢問(wèn)自己的祖輩，而白沉香通過(guò)她爺爺?shù)弥吞迫杏H戚，那么他們就不會(huì)再打起來(lái)，而是會(huì)聯(lián)盟，一起去打別的敵人，同樣，我的親戚是你，你的親戚是她，那么我和她也就會(huì)是親戚，就像老家里你堂哥是你親戚，你堂哥和他姥爺是親戚，那么你就和他姥爺是親戚

find實(shí)現(xiàn)

這個(gè)find就是用來(lái)查找他們的上級(jí)的，初始化時(shí)小怪獸高興壞了，認(rèn)為自己就是自己的上司，我就是王，我就是Boss，這么想其實(shí)也并沒(méi)有錯(cuò)，畢竟自己在井底，那么，就用數(shù)組pre[]來(lái)存他們的上一級(jí)，例如：pre[10]=6;那么就認(rèn)為10的上級(jí)就是6，6的上級(jí)假設(shè)是4，4的上級(jí)加入是自己，也即是 pre[4]=4;這時(shí)為4的怪獸就理解了，原來(lái)自己的上級(jí)是自己，那自己就是王了，這時(shí)就找到了boss,回想剛剛說(shuō)的，兩個(gè)怪獸如果想要打架，就需要先問(wèn)問(wèn)各自的上級(jí)，如果上級(jí)再問(wèn)上級(jí)直到問(wèn)到他們屬于同一個(gè)boss，這時(shí)它們就會(huì)微笑說(shuō)，原來(lái)我們屬于同一個(gè)領(lǐng)導(dǎo)，那么find就是用來(lái)找最終兩個(gè)分隊(duì)的怪獸最終的領(lǐng)導(dǎo)的

 public static int find(int x){
        if(pre[x]==x)return x;//如果上級(jí)領(lǐng)導(dǎo)是自己，就返回自己
        return pre[x]=find(pre[x]);//如果不是，就逐一進(jìn)行訪問(wèn)上級(jí)，直到找到boss,這里相當(dāng)于最終找到了boss,把boss賦值給pre[x]
    }

join的實(shí)現(xiàn)

join是用來(lái)干嘛的呢？它是用來(lái)合并的，加入有兩個(gè)大王，它們各自占山為王，勢(shì)力不相上下，實(shí)力也不相上下，有一天發(fā)生變故，大王1就想和大王2進(jìn)行合并，大王二琢磨著合并后誰(shuí)當(dāng)大王？不能讓它當(dāng)了大王，大王2于是就說(shuō)合并后我來(lái)當(dāng)大王，大王一顯然會(huì)不同意，大王二說(shuō)你來(lái)找我合并的，不同意也要同意，于是大王二當(dāng)成了 大王，這時(shí)大王二掌握了所有的軍隊(duì)，包括大王一的，那么join就是用來(lái)選兩個(gè)大王其中一個(gè)作為總大王的。

 public static void join(int x,int y){
        int xx=find(x);//用find找到第一個(gè)大王
        int yy=find(y);//找到第二個(gè)大王
        if(xx!=yy){//如果不相等
            pre[xx]=yy;//將其中一個(gè)大王統(tǒng)領(lǐng)第一個(gè)大王所有的軍隊(duì)
        }

整體代碼?

import java.util.Scanner;
public class test1 {
    static  int []pre=new int[10000];//注意題目中范圍
    public static void main(String[] args) {
        int n,m,p,x,y;
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();//n個(gè)人
        m=sc.nextInt();//m對(duì)關(guān)系
        p=sc.nextInt();//p詢問(wèn)關(guān)系
        for(int i = 0; i < n; i++){
            pre[i]=i;//初始化，自己的祖先是自己
        }
        for(int i = 0; i < m; i++){
            x=sc.nextInt();
            y= sc.nextInt();
            join(x,y);//合并
        }

        for(int i = 0; i <p;i++){
            x=sc.nextInt();
            y= sc.nextInt();
            if(find(x)==find(y)){
                System.out.print("Yes");
            }else{
                System.out.print("No");
            }
        }
    }
    public static int find(int x){
        if(pre[x]==x)return x;
        return pre[x]=find(pre[x]);
    }
    public static void join(int x,int y){
        int xx=find(x);
        int yy=find(y);
        if(xx!=yy){
            pre[xx]=yy;
        }
    }
} 

到此這篇關(guān)于Java實(shí)現(xiàn)并查集示例詳解的文章就介紹到這了,更多相關(guān)Java 并查集內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論