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

并查集入门精讲,实例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
分享到:
评论

相关推荐

    基于Simulink的风火水储联合调频系统中储能SOC对ACE影响的技术分析

    内容概要:本文详细探讨了在Simulink环境中构建的风火水储联合调频系统中,储能系统的荷电状态(SOC)对区域控制偏差(ACE)的影响。文中通过具体案例和MATLAB代码展示了储能系统在不同SOC水平下的表现及其对系统稳定性的作用。同时,文章比较了储能单独调频与风火水储联合调频的效果,强调了储能系统在应对风电波动性和提高系统响应速度方面的重要作用。此外,作者提出了针对SOC变化率的参数整定方法以及多电源协同工作的优化策略,旨在减少ACE波动并确保系统稳定运行。 适合人群:从事电力系统调频研究的专业人士,尤其是熟悉Simulink仿真工具的研究人员和技术人员。 使用场景及目标:适用于希望深入了解储能系统在电力系统调频中作用的研究者和技术人员,目标是通过合理的SOC管理和多电源协同工作,优化调频效果,提高系统稳定性。 其他说明:文章提供了详细的MATLAB代码片段,帮助读者更好地理解和应用所讨论的概念。同时,文中提到的实际案例和仿真结果为理论分析提供了有力支持。

    欧姆龙PLC NJ中大型程序案例:结构化与面向对象编程的深度融合及应用

    内容概要:本文深入探讨了欧姆龙PLC NJ系列中大型程序中结构化编程与面向对象编程的结合及其应用。首先介绍了结构化编程作为程序框架的基础,通过功能块(FB)实现清晰的程序结构和流程控制。接着阐述了面向对象编程的理念,将现实世界的对象映射到程序中,利用类的概念实现模块化和可扩展性。两者结合提高了程序的容错率,增强了程序的稳定性和可维护性。文中通过多个实际案例展示了如何在工业自动化领域中应用这两种编程方法,如电机控制、设备类的创建、异常处理机制、接口实现多态性、配方管理和报警处理等。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是那些希望提升PLC编程技能的人群。 使用场景及目标:适用于需要优化PLC程序结构、提高程序可靠性和可维护性的场合。目标是帮助工程师掌握结构化编程和面向对象编程的技巧,从而写出更加高效、稳定的PLC程序。 其他说明:文章强调了在实际项目中灵活运用两种编程方法的重要性,并提醒读者注意实时性要求高的动作控制应采用结构化编程,而工艺逻辑和HMI交互则更适合面向对象编程。

    matlab与聚类分析

    matlab与聚类分析。根据我国历年职工人数(单位:万人),使用有序样品的fisher法聚类。

    卡尔曼滤波生成航迹测量程序

    卡尔曼滤波生成航迹测量程序

    基于格子玻尔兹曼方法(LBM)的多孔电极浸润特性研究及其Python实现

    内容概要:本文详细介绍了利用格子玻尔兹曼方法(LBM)对多孔电极浸润特性的模拟研究。首先阐述了LBM的基本原理,包括碰撞和迁移两个关键步骤,并提供了相应的Python伪代码。接着讨论了如何处理多孔介质中的固体边界,特别是通过随机算法生成孔隙结构以及结合CT扫描数据进行三维重构的方法。文中还探讨了表面张力、接触角等因素对浸润过程的影响,并给出了具体的数学表达式。此外,文章提到了并行计算的应用,如使用CUDA加速大规模网格计算,以提高模拟效率。最后,作者分享了一些实用技巧,如通过调整松弛时间和润湿性参数来优化模拟效果,并强调了LBM在处理复杂几何结构方面的优势。 适合人群:从事电池研发、材料科学领域的研究人员和技术人员,尤其是关注多孔电极浸润性和电解液扩散机制的人群。 使用场景及目标:适用于希望深入了解多孔电极内部流体动力学行为的研究者,旨在帮助他们更好地理解和预测电极材料的浸润特性,从而改进电池设计和性能。 其他说明:尽管LBM在处理多孔介质方面表现出色,但在某些极端条件下仍需引入额外的修正项。同时,参数的选择和边界条件的设定对最终结果有着重要影响,因此需要谨慎对待。

    基于FPGA和W5500的TCP网络通信:Zynq扩展口开发测试平台(使用Vivado 2019.2纯Verilog实现)

    内容概要:本文详细介绍了在Zynq扩展口上使用FPGA和W5500实现TCP网络通信的过程。作者通过一系列实验和技术手段,解决了多个实际问题,最终实现了稳定的数据传输。主要内容包括:硬件搭建(SPI接口配置)、数据回环处理、压力测试及优化、多路复用扩展以及上位机测试脚本的编写。文中提供了大量Verilog代码片段,展示了如何通过状态机控制SPI通信、优化数据缓存管理、处理中断等问题。 适合人群:对FPGA开发和网络通信感兴趣的工程师,尤其是有一定Verilog编程基础的研发人员。 使用场景及目标:适用于需要在嵌入式系统中实现高效、稳定的TCP通信的应用场景。目标是帮助读者掌握FPGA与W5500结合进行网络通信的具体实现方法和技术细节。 其他说明:文章不仅提供了详细的代码实现,还分享了许多实践经验,如硬件连接注意事项、信号完整性问题的解决方案等。此外,作者还提到了未来的工作方向,如UDP组播和QoS优先级控制的实现。

    python3.10以上 可安装pyside6(类似pyqt),具体安装操作步骤

    python3.10以上 可安装pyside6(类似pyqt),具体安装操作步骤

    基于FDTD仿真的可调谐石墨烯超材料吸收体设计与实现

    内容概要:本文详细介绍了利用有限差分时域法(FDTD)进行可调谐石墨烯超材料吸收体的设计与仿真。文中解释了石墨烯超材料的基本结构(三层“三明治”结构)、关键参数(如化学势、周期、厚度等)及其对吸收性能的影响。同时展示了如何通过调整石墨烯的化学势来实现吸收峰的位置和强度的变化,以及如何优化结构参数以获得最佳的吸收效果。此外,还提供了具体的代码示例,帮助读者理解和重现相关实验结果。 适合人群:从事纳米光子学、超材料研究的专业人士,尤其是对石墨烯基超材料感兴趣的科研工作者和技术开发者。 使用场景及目标:适用于希望深入了解石墨烯超材料的工作原理及其潜在应用场景的研究人员;旨在探索新型可调谐光学器件的设计思路和发展方向。 其他说明:文中不仅分享了理论知识,还包括了许多实践经验,如避免常见错误、提高仿真相关效率的小技巧等。对于想要将研究成果应用于实际产品的团队来说,这些细节非常有价值。

    随机生成2字到10字的中文词组

    随机生成2字,3字,4字,5字,6字,7字,8字,9字,10字的中文词组20个

    【汽车电子电气架构】智能座舱域控平台设计:基于双片龍鷹一号SoC芯片的高性能硬件架构与多模态交互系统构建

    内容概要:本文详细探讨了智能座舱域控设计的发展历程和技术趋势。首先介绍了智能座舱从被动式交互到主动式交互的技术演变,包括硬件和交互方式的进步。随后,文章重点讨论了智能座舱功能发展趋势,涵盖车载显示技术的多屏化、大屏化和高端化,以及SoC芯片的多核异构架构和算力融合,强调了其在智能座舱中的核心作用。此外,还阐述了电子电气架构从分布式向集成化的转型,分析了其面临的挑战和未来趋势。最后,基于当前智能座舱的发展需求,提出了一种基于双片龍鷹一号芯片的新域控平台设计方案,详细描述了其硬件设计实现方案,旨在提供高性能、高可靠性的智能座舱解决方案。 适合人群:汽车电子工程师、智能座舱研发人员及相关领域的技术人员。 使用场景及目标:①帮助读者理解智能座舱的技术发展历程及其未来发展方向;②为智能座舱域控平台的设计和开发提供参考和技术支持;③探讨电子电气架构的转型对汽车行业的影响及应对策略。 其他说明:文章结合实际案例和技术数据,深入浅出地解释了智能座舱的各项技术细节,不仅提供了理论指导,还具有较强的实践意义。通过对智能座舱域控平台的全面剖析,有助于推动智能座舱技术的创新发展,提升用户体验。

    多智能体协同编队控制:无人机编队背后的Python实现与关键技术解析

    内容概要:本文详细介绍了多智能体协同编队控制的技术原理及其应用实例。首先通过生动形象的例子解释了编队控制的核心概念,如一致性算法、虚拟结构法和Leader-Follower模式。接着深入探讨了如何用Python实现基础的一致性控制,以及如何通过调整参数(如Kp、Ka)来优化编队效果。文中还讨论了实际工程中常见的问题,如通信延迟、避障策略和动态拓扑变化,并给出了相应的解决方案。最后,强调了参数调试的重要性,并分享了一些实用技巧,如预测补偿、力场融合算法和分布式控制策略。 适合人群:对多智能体系统、无人机编队控制感兴趣的科研人员、工程师和技术爱好者。 使用场景及目标:适用于希望深入了解多智能体协同编队控制理论并能够将其应用于实际项目的研究人员和开发者。目标是帮助读者掌握编队控制的关键技术和实现方法,提高系统的稳定性和可靠性。 其他说明:文章不仅提供了详细的理论讲解,还附有具体的代码示例,便于读者理解和实践。同时,作者结合自身经验分享了许多宝贵的调试技巧和注意事项,有助于读者在实际应用中少走弯路。

    评估管线钢环焊缝质量及其对氢脆的敏感性.pptx

    评估管线钢环焊缝质量及其对氢脆的敏感性.pptx

    C盘清理bat脚本自动清理C盘垃圾文件

    C盘清理bat脚本自动清理C盘垃圾文件

    GBT21266-2007 辣椒及辣椒制品中辣椒素类物质测定及辣度表示方法

    GBT21266-2007 辣椒及辣椒制品中辣椒素类物质测定及辣度表示方法

    弹跳球 XNA 游戏项目 演示如何使用 C# 在 Visual Studio XNA 中构建类似 arkanoiddx-ball 的游戏

    弹跳球 XNA 游戏项目。演示如何使用 C# 在 Visual Studio XNA 中构建类似 arkanoiddx-ball 的游戏。

    【人形机器人领域】宇树科技人形机器人:技术实力、市场炒作与应用前景分析

    内容概要:文章全面解析了宇树科技人形机器人的发展现状、技术实力、市场炒作现象及其应用前景和面临的挑战。宇树科技成立于2016年,凭借春晚舞台的惊艳亮相和社交媒体的热议迅速走红,其人形机器人具备先进的运动控制算法、传感器技术和仿生结构设计。然而,市场炒作现象如高价租赁、二手市场炒作和虚假宣传等影响了市场秩序。尽管存在炒作,人形机器人在工业、服务和家庭领域仍具广阔前景,但也面临技术升级、成本控制、安全性和政策监管等挑战。 适合人群:对机器人技术、人工智能以及科技发展趋势感兴趣的读者,包括科技爱好者、投资者和相关行业的从业者。 使用场景及目标:①帮助读者了解宇树科技人形机器人的技术特点和发展历程;②揭示市场炒作现象及其影响;③探讨人形机器人的应用前景和面临的挑战。 其他说明:文章强调了宇树科技人形机器人在技术上的突破和市场上的表现,同时也提醒读者关注市场炒作现象带来的风险,呼吁各方共同努力推动人形机器人产业健康发展。

    msvcp140.dll

    msvcp140.dll丢失怎样修复

    光学技术超透镜解决方案全球市场分析:前5强生产商排名及市场份额预测

    超透镜是一种将具有特殊电磁特性的纳米结构、按照一定方式进行排列的二维平面透镜,可实现对入射光振幅、相位、偏振等参量的灵活调控,在镜头模组、全息光学、AR/VR等方面具有重要应用,具有颠覆传统光学行业的潜力。 目前,超透镜解决方案的市场处于起步阶段,企业根据客户的具体需求和应用场景为其定制专用超透镜或超透镜产品。 根据QYResearch最新调研报告显示,预计2031年全球超透镜解决方案市场规模将达到29.26亿美元,未来几年年复合增长率CAGR为79.55%。 全球范围内,超透镜解决方案主要生产商包括Metalenz, Inc., Radiant Opto-Electronics (NIL Technology),迈塔兰斯、纳境科技、山河元景等,其中前五大厂商占有大约77.84%的市场份额。 目前,全球核心厂商主要分布在欧美和亚太地区。 就产品类型而言,目前红外超透镜解决方案是最主要的细分产品,占据大约96.76%的份额。 就产品类型而言,目前消费电子是最主要的需求来源,占据大约36.27%的份额。 主要驱动因素: 独特性能优势:超透镜解决方案具有更轻薄、成本更低、成像更好、更易集成、更高效及更易自由设计等优势。能以微米级厚度实现传统厘米级透镜功能,还可集多个光学元件功能于一身,大幅减小成像系统体积、重量,简化结构并优化性能。 技术创新推动:超透镜解决方案技术不断取得进步,设计技术和工艺水平持续提升,其性能和稳定性得以不断提高。制造工艺方面,电子束光刻等多种技术应用到超透镜解决方案生产中,推动超透镜解决方案向更高分辨率、更高产量、更大面积、更高性能的方向发展。 市场需求增长:消费电子、汽车电子、医疗、工业等众多领域快速发展,对高精度、高性能光学器件需求不断增加。如在手机摄像头中可缩小模组体积、提升成像分辨率和降低成本;在汽车电子领域能提高车载摄像头、激光雷达等传感器性能。

    MATLAB实现新能源并网的电力市场调度优化模型及其应用

    内容概要:本文详细介绍了基于MATLAB和优化工具Gurobi/Cplex实现的新能源并网电力市场调度模型。该模型通过IEEE30节点系统进行仿真,重点探讨了风电接入对传统火电调度的影响。文中展示了关键决策变量如机组启停状态、实时出力以及风电出力的定义方法,并深入解析了目标函数的设计,特别是总成本函数中燃料成本、启停成本、备用成本和弃风惩罚之间的权衡。此外,文章还讨论了直流潮流约束的作用,以及节点电价计算背后的经济学原理。最后,通过对不同情景的模拟实验,验证了模型的有效性和实用性。 适用人群:适用于从事电力系统研究、电力市场运营管理和新能源并网调度的专业人士和技术人员。 使用场景及目标:①帮助理解和掌握新能源并网对电力市场调度的具体影响;②为制定合理的电力市场规则和政策提供理论依据和技术支持;③指导实际电力系统的调度操作,提高系统运行效率和经济效益。 其他说明:文中提供的代码片段和具体实现细节有助于读者更好地理解模型的构造和求解过程。同时,强调了在实际应用中需要注意的问题,如弃风惩罚系数的选择、备用容量的配置等。

Global site tag (gtag.js) - Google Analytics