并查集-蒲公英云

并查集

Myth丶恋晨 2022-06-08 09:24 367阅读 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++;
    }
}