Java實現(xiàn)并查集示例詳解
題目
題目背景
若某個家族人員過于龐大,要判斷兩個是否是親戚,確實還很不容易,現(xiàn)在給出某個親戚關系圖,求任意給出的兩個人是否具有親戚關系。

思路
對于該題而言,考察的是并查集,也就是小怪獸逐個找上級領導的思路,指導找到最終的Boss停止下來,如果兩個怪獸要打架,需要問一問他們的上級領導,領導再問領導,逐級向上,最終發(fā)現(xiàn)它們屬于同一個Boss的部署的話就不能再打架了,這道題同樣的思路,如果斗羅大陸的一開始白沉香不知道唐三是親戚的話,他們就會先詢問自己的祖輩,而白沉香通過她爺爺?shù)弥吞迫杏H戚,那么他們就不會再打起來,而是會聯(lián)盟,一起去打別的敵人,同樣,我的親戚是你,你的親戚是她,那么我和她也就會是親戚,就像老家里你堂哥是你親戚,你堂哥和他姥爺是親戚,那么你就和他姥爺是親戚
find實現(xiàn)
這個find就是用來查找他們的上級的,初始化時小怪獸高興壞了,認為自己就是自己的上司,我就是王,我就是Boss,這么想其實也并沒有錯,畢竟自己在井底,那么,就用數(shù)組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的實現(xiàn)
join是用來干嘛的呢?它是用來合并的,加入有兩個大王,它們各自占山為王,勢力不相上下,實力也不相上下,有一天發(fā)生變故,大王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;//將其中一個大王統(tǒng)領第一個大王所有的軍隊
}
整體代碼?
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實現(xiàn)并查集示例詳解的文章就介紹到這了,更多相關Java 并查集內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
Mybatis foreach標簽使用不當導致異常的原因淺析
這篇文章主要介紹了Mybatis foreach標簽使用不當導致異常的原因探究,非常不錯,具有參考借鑒價值,需要的朋友可以參考下2016-12-12
SpringBoot中實現(xiàn)異步調用@Async詳解
這篇文章主要介紹了SpringBoot中實現(xiàn)異步調用@Async詳解,在SpringBoot的日常開發(fā)中,一般都是同步調用的,但實際中有很多場景非常適合使用異步來處理,需要的朋友可以參考下2024-01-01
MyEclipse8.6首次運行maven項目圖標上沒有小M的標識怎么解決
myeclipse8.6導入maven項目后識別為普通java項目,即項目圖標上沒有小M的標識。這時是無法直接運行的,怎么解決這一問題呢?下面小編給大家?guī)砹私鉀Q方案,需要的朋友參考下吧2016-11-11
Spring Boot與RabbitMQ結合實現(xiàn)延遲隊列的示例
本篇文章主要介紹了Spring Boot與RabbitMQ結合實現(xiàn)延遲隊列的示例,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-11-11
springboot之SpringApplication生命周期和事件機制解讀
這篇文章主要介紹了springboot之SpringApplication生命周期和事件機制,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2023-06-06

