`
128kj
  • 浏览: 601193 次
  • 来自: ...
社区版块
存档分类
最新评论

并查集入门精讲,实例2个(JAVA)

阅读更多
一、什么是并查集
   并查集:即不相交集合。一种简单的用途广泛的集合,实现了较快的合并和判断元素所在集合的操作,应用很多,如其求无向图的连通分量个数等。最完美的应用当属:实现Kruskar算法求最小生成树。

并查集实现方法:
   每个集合用一棵“有根树”表示;
   定义数组  int[] father
             int[] rank 
   father[i]=i,则i表示本集合且i是集合对应的树的根
   father[i]=j,则表示j是i的父节点
   rank[i]代表集合i的秩(比如子孙的多少或树的高度等),用于合并集合,秩小的合并到秩大的。

二、并查集的精髓(即它的三种操作):
1、Make_Set() 把每一个元素初始化为一个集合
    初始化后每一个元素的父亲节点是它本身。

    void Make_Set() {
     for(int i=0;i<father.length;i++){
       father[i] = i; //根据实际情况指定的父节点可变化
       rank[i] = 0; //根据实际情况初始化秩也有所变化
     } 
  }

2、Find_Set(x) 查找一个元素所在的集合
   查找一个元素所在的集合,其精髓是找到这个元素所在集合的祖先!
   判断两个元素是否属于同一集合,只要看他们所在集合的祖先是否相同即可。
   合并两个集合,也是使一个集合的祖先成为另一个集合的祖先

  //递归实现找祖先
  int Find_Set(int x){
    if (x != father[x]){
     father[x] = Find_Set(father[x]);//这个回溯时的压缩路径是精华,将查找路径的所有节点都指向根节点
    }
    return father[x];
   }


  //循环实现找祖先

  int Find_Set(int x)
{
    int root=x;
    while(father[root]!=root)
        root=father[root];
    return root;
  }

   //循环实现找祖先,路径压缩
   //每次查找的时候,如果路径较长,则修改信息,以便下次查找的时候速度更快
   //第一步,找到根节点;第二步,修改查找路径上的所有节点,将它们都指向根结点
   int Find_Set(int x){
     int k,root;
     root=x;
     while(root!=father[root])  //循环找x的根     
         root=father[root];
     while(x!=root)//本循环修改查找路径中的所有节点使其指向根节点---压缩
     {
         k=father[x];
         father[x]=root;//指向根节点
         x=k;
     }
     return x;
    }

路径压缩示意图:



3、Union(x,y) 合并x,y所在的两个集合
  合并两个不相交集合操作很简单:
  利用Find_Set找到其中两个集合的祖先,将一个集合的祖先指向另一个集合的祖先。

void Union(int x, int y){//合并集合的条件要试具体问题而定,这里将秩小的合并到秩大的。
    x = Find_Set(x);
    y = Find_Set(y);
    if (x == y) return;
    if (rank[x] > rank[y]) {  
            father[y] = x;  
     } else if (rank[x] < rank[y]) {  
            father[x] = y;  
     } else {  
            rank[y]++;  
            father[x] =y;  
     }  

}


三、并查集的优化
1、Find_Set(x)时路径压缩
   寻找祖先时我们一般采用递归查找,但是当元素很多亦或是整棵树变为一条链时,每次Find_Set(x)都是O(n)的复杂度,有没有办法减小这个复杂度呢?
答案是肯定的,这就是路径压缩,即当我们经过"递推"找到祖先节点后,"回溯"的时候顺便将它的子孙节点都直接指向祖先,
这样以后再次Find_Set(x)时复杂度就变成O(1)了。

2、Union(x,y)时按秩合并
即合并的时候将元素少的集合合并到元素多的集合中,这样合并之后树的高度会相对较小。


实例一:判断亲戚关系.
   若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。

规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。

    先输入10个人(编号从1-10)及7组亲戚关系,然后输入3组数据,问这三组数据是不是亲戚关系?

输入
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9

输出
Yes
No
Yes

分析:其实本题只是一个对分离集合(并查集)操作的问题。我们可以给每个人建立一个集合,集合的元素值有他自己,表示最开始时他不知道任何人是它的亲戚。以后每次给出一个亲戚关系a, b,则a和他的亲戚与b和他的亲戚就互为亲戚了,将a所在集合与b所在集合合并。

    最后我们得到3个集合{1,2,3,4}, {5,6,7}, {8,9},于是判断两个人是否亲戚的问题就变成判断两个数是否在同一个集合中的问题。
import java.util.Scanner;
   public class Main{
     int[] father;
     int[] rank;

    public Main(){
       }
 
    public void go(){
      Scanner in=new Scanner(System.in);
       int n=in.nextInt();
       int m=in.nextInt();
       father=new int[n+1];
       rank=new int[n+1];
        Make_Set();
       for(int i=1;i<=m;i++){
           int a=in.nextInt();
           int b=in.nextInt();
           int x=Find_Set(a);
           int y=Find_Set(b);
           Union(x,y);
       }
       //for(int i=1;i<=n;i++)
       //  System.out.print("father["+i+"]="+father[i]+"  ");
       int k=in.nextInt();
       for(int i=1;i<=k;i++){
           int x=in.nextInt();
           int y=in.nextInt();
           if(Find_Set(x)==Find_Set(y)) System.out.println("Yes");
           else  System.out.println("No");
       }
     }
    
       
    private void Make_Set() {
     for(int i=0;i<father.length;i++){
       father[i] = i; //根据实际情况指定的父节点可变化
       rank[i] = 0; //根据实际情况初始化秩也有所变化
     }  
    }
  
    private int Find_Set(int x){
     if (x != father[x]){
       father[x] = Find_Set(father[x]);//这个回溯时的压缩路径是精华,将查找路径的所有节点都指向根节点
      }
     return father[x];
    }

    void Union(int x, int y){
      int f1 = Find_Set(x);
      int f2 = Find_Set(y);
       if(f1!=f2) father[f1]=f2;
    
    }

  
     public static void main(String args[]){
        Main m=new Main();
        m.go();
     }
  }


实例二:
   上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从5到达8。



Input
输入包含多组数据,每组数据是一个以0 0结尾的整数对列表,表示了一条通道连接的两个房间的编号。房间的编号至少为1,且不超过100000。每两组数据之间有一个空行。
整个文件以两个-1结尾。

Output
对于输入的每一组数据,输出仅包括一行。如果该迷宫符合小希的思路,那么输出"Yes",否则输出"No"。

Sample Input
6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0

-1 -1


Sample Output
Yes
Yes
No


解题思路:题目意思是判断是不是连通无环的图,使用并查集合并所有顶点.
1》判断成环的时候,只要判断输入边的两个点。有一个共同的父节点,那么这两个点就成环。

2》判断连通的时候,只要判断根节点数为1即可。

注意:当输入的这组数据只有 0 0 时,依然是满足条件的,即应输出 "Yes"。

import java.util.Scanner;
import java.io.*;

public class Main {
    private final static int max = 100001;
    private int[] f;
    private int[] set;
    private int[] height;
    private int flag;

        public Main(){
           set = new int[max];
           height = new int[max];
           f = new int[max];
           flag = 1;
        }

    // 初始化集合
    private  void init() {
        for (int i = 1; i < max; i++) {
            set[i] = i;
            f[i] = 0;
            height[i] = 1;
        }
    }

    // 查找x属于哪个集合,循环实现,防暴栈.
    private  int find(int x) {
        while (set[x] != x)
            x = set[x];
        return x;
    }

    // 合并集合
    private  void merge(int a, int b) {
        if (height[a] < height[b])
            set[a] = b;
        else if (height[a] > height[b])
            set[b] = a;
        else {
            set[b] = a;
            height[a]++;
        }
    }

    public void go() {
        Scanner in= new Scanner(System.in);
        while (true) {
            int a =in.nextInt();
            int b = in.nextInt();
            if (a == -1 && b == -1)break;
            if (a == 0 && b == 0) {System.out.println("Yes");continue;}
            
            init();
            
            f[a] = f[b] = 1;//标记a,b已使用
            flag=1;
            a = find(a);
            b = find(b);
            if (a != b)
                merge(a, b);//合并
            else //存在环
                flag = 0;
            
            while (true) {
                
                a = in.nextInt();
                b =in.nextInt();
                if (a == 0 && b == 0)
                    break;
                a = find(a);
                b = find(b);
                if(a!=b)
                    merge(a, b);
                else //存在环
                    flag = 0;
                f[a] = f[b] = 1;
            }
            int k = 0;
            for (int i = 1; i < max; i++) {//统计树根的数目
                if (f[i]==1 && set[i] == i)
                    k++;
                if(k>1){flag = 0;break;}
            }
            if (flag==1)
                System.out.println("Yes");
            else
                System.out.println("No");
        }

    }
    public static void main(String args[]){
        Main m=new Main();
       m.go();
    }

}
  • 大小: 11.1 KB
  • 大小: 13.9 KB
0
0
分享到:
评论

相关推荐

    基于springboot教育资源共享平台源码数据库文档.zip

    基于springboot教育资源共享平台源码数据库文档.zip

    视频笔记linux开发篇

    linux开发篇,配套视频:https://www.bilibili.com/list/474327672?sid=4493702&spm_id_from=333.999.0.0&desc=1

    readera-24-09-08plus2020.apk

    ReadEra 这个阅读应用能够打开下列任何格式的文档: EPUB, PDF, DOC, RTF, TXT, DJVU, FB2, MOBI, 和 CHM. 基本上来说,你可以用它阅读你的设备内存中的任何书籍或者文本文档。 这个应用与划分成章节的文档兼。,有一个书签功能,可以在你阅读的时候,自动保存你的进度。另外,它让你更改页面模式,从几种不同的主题中进行挑选(夜间,白天,棕黑色调,还有控制台)。

    STM32单片机控制舵机旋转

    软件环境:KEIL4 硬件环境:STM32单片机+舵机 控制原理:通过控制输出信号的占空比调节舵机旋转的角度

    基于springboot仓库管理系统源码数据库文档.zip

    基于springboot仓库管理系统源码数据库文档.zip

    酒店管理系统源码C++实现的毕业设计项目源码.zip

    酒店管理系统源码C++实现的毕业设计项目源码.zip,个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。 酒店管理系统源码C++实现的毕业设计项目源码.zip,酒店管理系统源码C++实现的毕业设计项目源码.zip个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。酒店管理系统源码C++实现的毕业设计项目源码.zip酒店管理系统源码C++实现的毕业设计项目源码.zip酒店管理系统源码C++实现的毕业设计项目源码.zip,个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。酒店管理系统源码C++实现的毕业设计项目源码.zip,个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕

    58商铺全新UI试客试用平台网站源码

    58商铺全新UI试客试用平台网站源码

    基于SpringBoot+Vue的轻量级定时任务管理系统.zip

    springboot vue3前后端分离 基于SpringBoot+Vue的轻量级定时任务管理系统.zip

    毕业设计&课设_微博情感分析,用 flask 构建 restful api,含相关算法及数据文件.zip

    该资源内项目源码是个人的课程设计、毕业设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载使用! ## 项目备注 1、该资源内项目代码都经过严格测试运行成功才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。

    4D毫米波雷达点云数据处理方法研究.caj

    4D毫米波雷达点云数据处理方法研究.caj

    S M 2 2 5 8 X T量产工具

    S M 2 2 5 8 X T 量产工具供大家下载使用

    基于springboot的文物管理系统源码数据库文档.zip

    基于springboot的文物管理系统源码数据库文档.zip

    基于springboot的电影院售票管理系统源码数据库文档.zip

    基于springboot的电影院售票管理系统源码数据库文档.zip

    Javaweb仓库管理系统项目源码.zip

    基于Java web 实现的仓库管理系统源码,适用于初学者了解Java web的开发过程以及仓库管理系统的实现。

    美容美发项目,使用django框架,前后端一体化项目

    美容美发项目,使用django框架,前后端一体化项目

    2023年中国在线票务行业市场规模约为24.99亿元,挖掘市场新机遇

    在线票务:2023年中国在线票务行业市场规模约为24.99亿元,挖掘市场蓝海新机遇 在数字浪潮的席卷下,传统的票务销售模式正经历着前所未有的变革。纸质门票逐渐淡出人们的视野,取而代之的是便捷、高效的数字和移动票务。这一转变不仅为消费者带来了前所未有的购票体验,更为在线票务平台开辟了广阔的发展空间和市场机遇。随着国民经济的持续增长和文体娱乐行业的蓬勃发展,中国在线票务行业正站在时代的风口浪尖,等待着每一位有志之士的加入。那么,这片蓝海市场究竟蕴藏着怎样的潜力?又该如何把握机遇,实现突破?让我们一同探索。 市场概况: 近年来,中国在线票务行业市场规模持续扩大,展现出强劲的增长势头。据QYResearch数据显示,2023年中国在线票务行业市场规模约为24.99亿元,尽管受到宏观经济的影响,市场规模增速放缓,但整体趋势依然向好。这一增长主要得益于国民人均收入的不断提高、电影及演出行业的快速发展以及政府政策的支持。例如,2023年财政部、国家电影局发布的《关于阶段性免征国家电影事业发展专项资金政策的公告》,为电影行业注入了强劲动力,进而推动了在线票务市场规模的扩大。 技术创新与趋势: 技术进步

    基于SpringBoot的养老院管理系统源码数据库文档.zip

    基于SpringBoot的养老院管理系统源码数据库文档.zip

    毕业设计&课设_含构建设置及相关操作,基于特定技术,具体功能未详细说明.zip

    该资源内项目源码是个人的课程设计、毕业设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载使用! ## 项目备注 1、该资源内项目代码都经过严格测试运行成功才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。

    Go语言入门指南:基础语法、并发编程详解

    内容概要:本文档是一份详细的Go语言教程,从基础概念介绍到高级主题均有覆盖。主要内容包括Go语言的基础语法、数据类型、控制结构、函数、结构体、接口和并发编程等方面。通过具体示例介绍了如何使用Go语言进行开发。 适合人群:初学者和有一定经验的程序员都可以从这篇教程中受益,特别是那些想要快速掌握Go语言并应用于实际项目的开发者。 使用场景及目标:适用于初学者系统学习Go语言的基础知识和常用功能;也可以作为已有开发经验者的参考资料,帮助他们解决具体的编程问题,提高开发效率。 其他说明:本教程不仅包含了Go语言的基本知识点,还重点讲解了其独特的并发编程模型。读者在学习过程中应该注重理论与实践相结合,通过实际编写代码来加深理解和记忆。

    基于springboot计算机基础网上考试系统源码数据库文档.zip

    基于springboot计算机基础网上考试系统源码数据库文档.zip

Global site tag (gtag.js) - Google Analytics