并查集

Myth丶恋晨 2022-06-08 09:24 285阅读 0赞

> 题目  
> 某学校近期要组织全校同学出去参加某项活动，由于人数众多，学校决定让同学们自行组队，以小组为单位进行活动。假设学校一共n个同学，每个同学有一个唯一的数字作为标签，标签数字范围1到n。为了统计分组情况，学校要求有分组意愿的同学提交一个数字，表示其会和以该数字为标签的同学分到一组。  
> 现在告诉你每位同学的选择，你能统计出一共有多少个小组么？  
> 注意如果1和2一组，2和3一组，那么1，2，3属于一组。默认自己一定和自己在一组。  
> 输入  
> 输入包括两行，第一行是同学的个数n  
> 第二行一共有n个数，分别代表第i个同学愿意和哪个同学组队  
> 输出  
> 输出包括一个整数，表示组的队数

这是一道经典的并查集算法，以下为代码

import java.util.Scanner;
    
    public class Main {
        
        static int[] pre ;
        static int[] t;
        static int count;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int[] array = new int[n];
            pre =  new int[n+1];//记录前导点
            for (int i = 1; i <= n; i++) {
       //初始化前导点
                pre[i] = i;
            }
            for (int i = 0; i < n; i++) {
                array[i] = in.nextInt();
                union(i+1, array[i]);
            }
            t = new int[n+1];//记录根节点
            for (int i = 1; i <= n; i++) {
                t[pre[i]] = 1;
            }
            for (int i = 0; i < n; i++) {
                if(t[i] == 1)
                    count++;
            }
            System.out.println(count);
        }
        /**
         * 查找根节点
         * @param x
         * @return
         */
        private static int find(int x){
            int r = x;
            while(pre[r]!=r){
                r = pre[r];
            }
            int i = x,j;
            while(i!=r){
       //更新前驱节点为根节点
                j = pre[i];
                pre[i] = r;
                i = j;
            }
            return r;
        }
        private static void union(int x, int y){
            int fx = find(x);
            int fy = find(y);
            if(fx!=fy)//如果根节点不同则合并
                pre[fx] = fy;
        }
    }

并查集通常还会用来判断是否有环，例如下题

> 题目：在一个王国里，建立很多瞭望塔，瞭望塔之间连接有围墙。给出瞭望塔个数n，各个塔之间的围墙数m。接着给出m组A B；  
> 表示A B之间有围墙连接，问这些哨塔，围墙把土地分割成了几个部分。

土地被分割成几部分其实就是指有多少个环，对于并查集查找函数，如果两个节点的父节点不相同，则合并这两个节点所在集合，否则说明这两个节点之间原本就存在通路，再加上这条边就组成了环。  
代码如下：

import java.util.Scanner;
    
    public class Main {
        
        static int[] pre ;
        static int count;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            int[] array = new int[n];
            pre =  new int[n+1];//记录前导点
            for (int i = 1; i <= n; i++) {
       //初始化前导点
                pre[i] = i;
            }
            for (int i = 0; i < m; i++) {
                int a = in.nextInt();
                int b = in.nextInt();
                union(a, b);
            }
            System.out.println(count);
        }
        /**
         * 查找根节点
         * @param x
         * @return
         */
        private static int find(int x){
            int r = x;
            while(pre[r]!=r){
                r = pre[r];
            }
            return r;
        }
        private static void union(int x, int y){
            int fx = find(x);
            int fy = find(y);
            if(fx!=fy)//如果根节点不同则合并
                pre[fx] = fy;
            else
                count++;
        }
    }