链接

给定一个没有重复值的整形数组arr，初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构，并提供以下两个操作。
boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合
void union(int a, int b): 把a所在的集合与b所在的集合合并在一起，原本两个集合各自的元素以后都算作同一个集合

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;
import java.util.Map;


public class Main {

    private static final StreamTokenizer TOKENIZER =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    private static int nextInt() {
        try {
            TOKENIZER.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) TOKENIZER.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int m = nextInt();
        UnionSet<Integer> unionSet = new UnionSet<>();
        for (int i = 1; i <= n; ++i) {
            unionSet.add(i);
        }

        while (m-- > 0) {
            int op = nextInt();
            int a = nextInt();
            int b = nextInt();
            if (op == 1) {
                System.out.println(unionSet.inSameSet(a, b) ? "Yes" : "No");
            } else {
                unionSet.union(a, b);
            }
        }
    }
}

class UnionSet<V> {

    private Map<V, V> parentMap = new HashMap<>();

    private Map<V, Integer> sizeMap = new HashMap<>();

    public void add(V v) {
        parentMap.put(v, v);
        sizeMap.put(v, 1);
    }

    public void build(V[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        for (V item : arr) {
            parentMap.put(item, item);
            sizeMap.put(item, 1);
        }
    }

    public boolean inSameSet(V v1, V v2) {
        V parentV1 = find(v1);
        V parentV2 = find(v2);
        if (parentV1 == null || parentV2 == null) {
            return false;
        }
        return parentV1 == parentV2;
    }

    private V findPlus(V x) {
        V root = parentMap.get(x);
        while (root != parentMap.get(root)) {
            root = parentMap.get(root);
        }
        while (x != root) {
            V father = parentMap.get(x);
            parentMap.put(x, root);
            x = father;
        }
        return root;
    }

    public V find(V x) {
        V parent = parentMap.get(x);
        if (parent == x) {
            return parent;
        }
        parent = find(parent);
        parentMap.put(x, parent);
        return parent;
    }

    public void union(V v1, V v2) {
        V parentV1 = find(v1);
        V parentV2 = find(v2);
        if (parentV1 == null || parentV2 == null || parentV1 == parentV2) {
            return;
        }

        int sizeV1 = sizeMap.get(parentV1);
        int sizeV2 = sizeMap.get(parentV2);
        if (sizeV1 >= sizeV2) {
            parentMap.put(parentV2, parentV1);
            sizeMap.put(parentV1, sizeV1 + sizeV2);
            sizeMap.remove(parentV2);
        } else {
            parentMap.put(parentV1, parentV2);
            sizeMap.put(parentV2, sizeV1 + sizeV2);
            sizeMap.remove(parentV1);
        }
    }

    public int size() {
        return sizeMap.size();
    }
}

class Union {
    private int[] parent;
    private int[] size;

    public Union(int n) {
        parent = new int[n + 1];
        size = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
            size[i] = 1;
        }
    }

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

    public boolean inSameSet(int a, int b) {
        return find(a) == find(b);
    }

    public void union(int a, int b) {
        int p1 = find(a);
        int p2 = find(b);
        if (p1 == p2) {
            return;
        }
        if (size[p1] >= size[p2]) {
            parent[p2] = p1;
            size[p1] = size[p1] + size[p2];
        } else {
            parent[p1] = p2;
            size[p2] = size[p1] + size[p2];
        }
    }
}