核心操作

    //路径压缩
    static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    static void merge(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb) return;
        p[pa] = pb;
        size[pb] += size[pa];
    }

    //启发式合并
    static void merge(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb) return;
        if (size[pa] < size[pb]) {//按照节点合并，也可以直接合并，影响不大
            p[pa] = pb;
            size[pb] += size[pa];
        } else {
            p[pb] = pa;
            size[pa] += size[pb];
        }
    }

模板题

import java.util.*;
import java.io.*;


public class Main {

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static final int N = 100010;
    static int n, m;
    static int[] p = new int[N];

    public static void main(String[] args) throws IOException{

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(), m = sc.nextInt();

        for (int i = 1; i <= n; i++) p[i] = i;

        while (m-- > 0) {
            char op = sc.next().charAt(0);
            int a = sc.nextInt(), b = sc.nextInt();
            if (op == 'M') p[find(a)] = find(b);
            else {
                if (find(a) == find(b)) bw.write("Yes\n");
                else bw.write("No\n");
            }
        }
        bw.flush();
    }

    public static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

带权并查集

银河英雄传说

推导部分和

应用题

格子游戏

搭配购买(并查集+01背包)

程序自动分析(并查集+离散化)