什么样的题目使用并查集

  1. 关于集合合并
  2. 判断在不在同一个集合中
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class UnionFind {
        HashMap<Integer, Integer> fathers = new HashMap<>();
        public UnionFind(Set<Integer> set) {
            for (int n : set) {
                fathers.put(n, n);
            }
        }
        public void union(int x, int y) {
            int fa_x = find(x);
            int fa_y = find(y);
            fathers.put(fa_x, fa_y);
        }
        public int find(int x) {
            int father = fathers.get(x);
            while (father != fathers.get(father)) {
                father = fathers.get(father);
            }
            while (fathers.get(x) != father) {
                int tmp = fathers.get(x);
                fathers.put(x, father);
                x = tmp;
            }
            return father;
        }
    }