什么样的题目使用并查集

  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;
    }
    }