并查集

并查集的功能

1. 合并(Union): 合并两个集合,
2. 查询(Find): 查询某个元素是否在集合中.

核心要点

1. 以树的形式维护集合.
2. 集合的编号为根节点的编号. 根节点为代表元素.
3. 每个节点都保存其父节点的编号, 用于查找元素属于的集合.

用什么数据结构存储?

使用数组进行维护.

// 并查集
int[] p;

// 并查集大小(可选)
int[] size;

如何判断树根?

public boolean isRoot(int x) {
    return p[x] == x;
}

如何求元素对应的集合编号?

// 这里进行了路径压缩: 通过某个路径找到根节点, 则将该路径上的所有节点都指向根节点.
public int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }

    return p[x];
}

如何合并集合?

// 将 x 所在的集合和 y 所在的集合合并
public void merge(int x, int y) {
    p[find(x)] = find(y);
    // 或者 p[find(y)] = find(x);
}

例题

合并集合-acwing

合并集合-acwing

public class acwing_838 {

    int[] p;

    int n, m;

    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public void mergeCollections() throws IOException {
        String nums = reader.readLine();
        String[] numsSplit = nums.split(" ");

        n = Integer.parseInt(numsSplit[0]);
        m = Integer.parseInt(numsSplit[1]);

        p = new int[n + 1];

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

        List<String> res = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            String op = reader.readLine();
            String[] ops = op.split(" ");
            if (ops[0].equals("M")) {
                merge(Integer.parseInt(ops[1]), Integer.parseInt(ops[2]));
            } else if (ops[0].equals("Q")) {
                res.add(find(Integer.parseInt(ops[1])) == find(Integer.parseInt(ops[2])) ? "Yes" : "No");
            }
        }

        res.forEach(System.out::println);
    }

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

        return p[x];
    }

    void merge(int x, int y) {
        p[find(x)] = find(y);
    }

    public static void main(String[] args) {
        acwing_838 acwing838 = new acwing_838();
        try {
            acwing838.mergeCollections();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}