Java實現並查集示例詳解

Posted on by

題目

題目背景

若某個傢族人員過於龐大，要判斷兩個是否是親戚，確實還很不容易，現在給出某個親戚關系圖，求任意給出的兩個人是否具有親戚關系。

思路

對於該題而言，考察的是並查集，也就是小怪獸逐個找上級領導的思路，指導找到最終的Boss停止下來，如果兩個怪獸要打架，需要問一問他們的上級領導，領導再問領導，逐級向上，最終發現它們屬於同一個Boss的部署的話就不能再打架瞭，這道題同樣的思路，如果鬥羅大陸的一開始白沉香不知道唐三是親戚的話，他們就會先詢問自己的祖輩，而白沉香通過她爺爺得知她和唐三有親戚，那麼他們就不會再打起來，而是會聯盟，一起去打別的敵人，同樣，我的親戚是你，你的親戚是她，那麼我和她也就會是親戚，就像老傢裡你堂哥是你親戚，你堂哥和他姥爺是親戚，那麼你就和他姥爺是親戚

find實現

這個find就是用來查找他們的上級的，初始化時小怪獸高興壞瞭，認為自己就是自己的上司，我就是王，我就是Boss，這麼想其實也並沒有錯，畢竟自己在井底，那麼，就用數組pre[]來存他們的上一級，例如：pre[10]=6;那麼就認為10的上級就是6，6的上級假設是4，4的上級加入是自己，也即是 pre[4]=4;這時為4的怪獸就理解瞭，原來自己的上級是自己，那自己就是王瞭，這時就找到瞭boss,回想剛剛說的，兩個怪獸如果想要打架，就需要先問問各自的上級，如果上級再問上級直到問到他們屬於同一個boss，這時它們就會微笑說，原來我們屬於同一個領導，那麼find就是用來找最終兩個分隊的怪獸最終的領導的

 public static int find(int x){
        if(pre[x]==x)return x;//如果上級領導是自己，就返回自己
        return pre[x]=find(pre[x]);//如果不是，就逐一進行訪問上級，直到找到boss,這裡相當於最終找到瞭boss,把boss賦值給pre[x]
    }

join的實現

join是用來幹嘛的呢？它是用來合並的，加入有兩個大王，它們各自占山為王，勢力不相上下，實力也不相上下，有一天發生變故，大王1就想和大王2進行合並，大王二琢磨著合並後誰當大王？不能讓它當瞭大王，大王2於是就說合並後我來當大王，大王一顯然會不同意，大王二說你來找我合並的，不同意也要同意，於是大王二當成瞭 大王，這時大王二掌握瞭所有的軍隊，包括大王一的，那麼join就是用來選兩個大王其中一個作為總大王的。

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

整體代碼 

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個人
        m=sc.nextInt();//m對關系
        p=sc.nextInt();//p詢問關系
        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;
        }
    }
}

到此這篇關於Java實現並查集示例詳解的文章就介紹到這瞭,更多相關Java 並查集內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：