并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

基础的：hdu1232

参考博客https://www.cnblogs.com/xzxl/p/7226557.html

import java.*;import java.util.*;public class Main91 {    static int[] pre;    static int[] rank;    public static void init(int n) {        pre = new int[n + 1];        rank = new int[n + 1];        for (int i = 0; i < pre.length; i++) {            pre[i] = i;            rank[i] = 1;        }    }    public static void Union(int x, int y) {        int a = find(x);        int b = find(y);        if (a == b)            return;        if (rank[a] > rank[b]) {            pre[b] = a;        } else if (rank[b] > rank[a]) {            pre[a] = b;        } else {            pre[a] = b;            rank[b]++;        }        // return ;    }    public static int find(int x) {        if (pre[x] == x) {            return x;        }        return pre[x] = find(pre[x]);    }    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        while (true) {            int n = sc.nextInt();            init(n);            if (n == 0)                break;            int m = sc.nextInt();            // pre = new int[n+1];            int count = 0;            for (int i = 0; i < m; i++) {                int x = sc.nextInt();                int y = sc.nextInt();                Union(x, y);            }            for (int i = 1; i <= n; i++) {                if (pre[i] == i) {                    count++;                }            }            System.out.println(count - 1);        }    }}