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

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

相关推荐

    Java ME 移动开发实例精讲

    《Java ME 移动开发实例精讲》显然是一个教程资源,包含了视频教学和源代码示例,由郭克华编著,旨在帮助学习者深入理解和实践Java ME编程。 Java ME的开发主要包括以下几个关键知识点: 1. **基础环境搭建**:...

    ADAMS 入门到精通实例精讲二 仿真源文件

    总的来说,ADAMS入门到精通实例精讲二的目的是帮助学习者熟练掌握ADAMS软件,通过一系列实例,逐步提升对多体动力学仿真技能的掌握。在学习过程中,不仅要理解软件的操作,更要学会如何将理论知识与实际问题相结合,...

    Java程序设计精讲课件

    总之,这个Java程序设计精讲课程覆盖了从入门到进阶的关键知识点,对于想要全面掌握Java编程的人来说是一份宝贵的资源。配合源代码的实践,学习者可以更深入地理解每个概念,并提升自己的编程技能。通过学习和实践,...

    Java基础教案\JAVA精讲入门

    5.第1个Java程序:编程实例操作示范,向学生示范编写、编译与运行Java程序的3个完整步骤。强调Java程序的命名规则。 6.示范结束后,学生模仿编写程序; 7.分析Java运行过程,再次讲解Jvm、字节码等概念 8.简单...

    Java Web开发之Struts编程基础与实例精讲 part2

    Java Web开发之Struts编程基础与实例精讲 part2 本书分成了3个part,请将这个3个part下载完以后,按照顺序修改名称例如1.rar 2.rar 3.rar就可以解压缩了。

    最全java面试教程集合,含java面试题精讲ppt、大厂Java面试300题、基本java简历模板等

    最全java面试教程集合,含java面试题精讲ppt、大厂Java面试300题、基本java简历模板等 最全java面试教程集合,含java面试题精讲ppt、大厂Java面试300题、基本java简历模板等 最全java面试教程集合,含java面试题精讲...

    单片机35个实例精讲

    在本“单片机35个实例精讲”中,我们将深入探讨一系列实用且具有代表性的单片机应用案例,旨在帮助学习者掌握单片机的基础知识与实践技能。 首先,单片机的核心是中央处理器(CPU),它执行存储在内存中的指令来...

    JSP+Oracle网站开发实例精讲

    【JSP+Oracle网站开发实例精讲】 JSP(JavaServer Pages)是Java技术在Web开发中的一个重要应用,它允许开发者将动态代码嵌入到静态HTML页面中,从而实现动态网页的生成。Oracle则是一种广泛使用的大型关系型数据库...

    VC++ MFC入门精讲.PPT

    VC++ MFC入门精讲课件,看了不后悔,真的很实用哦!!

    JAVA虚拟机精讲

    JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA虚拟机精讲JAVA...

    COM 编程入门精讲

    COM 编程入门精讲 COM 编程入门精讲是为刚刚接触 COM 的程序员提供编程指南,帮助...COM 编程入门精讲为程序员提供了一个系统的 COM 编程指南,帮助他们快速掌握 COM 的基本概念和技术,提高编程效率和代码复用性。

    EXCEL 2007 VBA入门与范例精讲_第2部分 共2部分.

    EXCEL 2007 VBA入门与范例精讲_第2部分 共2部分

    HACK编程实例精讲

    《HACK编程实例精讲》是一本旨在帮助读者掌握编程技巧,并能应用于网络和系统安全领域的书籍。作者宋柏思,以网名谷夕、gxisone,在书中不仅分享了个人的学习经历,也详细讲解了通过阅读和写作代码成为编程高手的...

    java核心技术精讲

    'Java核心技术精讲'是一本实战型的、接近以自学为主的Java核心入门类图书。全书内容包括Java简介、Java基础语法、面向对象、异常的捕获及处理、包及访问控制限、Java新特性、多线程、常用类库、JavaIO操作、网络编程...

    ITIL 入门到精通 有实例精讲

    本教程“ITIL 入门到精通 有实例精讲”涵盖了ITIL的核心概念、流程和最佳实践,通过实例帮助学习者深入理解和应用。 一、ITIL基础 ITIL由五个主要阶段组成:服务战略、服务设计、服务转换、服务运营和服务改进。...

    ARM嵌入式常用模块与综合系统设计实例精讲2(pdf)

    全书针对目前通用流行的ARM嵌入式处理器,通过实例精讲的形式,详细介绍了ARM嵌入式常用模块与综合应用系统设计的方法与技巧。  全书共分3篇26章,第一篇为基础知识篇,简要介绍了ARM 处理器及系统结构、ARM编程...

    嵌入式Linux驱动程序和系统开发(精讲实例)_源码

    本资源提供了精讲实例的源码,旨在帮助开发者深入理解和实践这一领域的核心技能。以下是对各章节内容的详细解读: 1. **第9章:USB驱动** - USB(通用串行总线)是现代计算机与外部设备交互的主要接口之一。这一章...

    hack编程实例精讲2源代码.rar

    hack编程实例精讲2源代码.rar 关于hack编程的好资料

    Verilog HDL应用程序设计实例精讲

    每个模块可以有输入、输出端口,并可以通过实例化其他模块来构建更复杂的系统。例如,你可以定义一个加法器模块,然后在更高层次的设计中使用这个加法器模块来构建计算器。 设计流程中,了解如何进行仿真也是必不可...

Global site tag (gtag.js) - Google Analytics