class Solution {

    Map<Integer, Integer> node2root = new HashMap<>();
    public void union(Integer num1, Integer num2) {
        add(num1);
        add(num2);

        Integer root1 = find_root(num1);
        Integer root2 = find_root(num2);

        if (root1 == root2) return;

        node2root.put(root1, root2);
    }

    public void add(Integer num1) {
        if (node2root.containsKey(num1)) return;
        node2root.put(num1, num1);
    }

    public Integer find_root(Integer num1) {
        Integer root_now = node2root.get(num1);
        if (root_now == num1) return num1;

        node2root.put(num1, find_root(root_now)); // attention: put root_now here instead of num1 again

        return node2root.get(num1);
    }

    public boolean validTree(int n, int[][] edges) {
        // a tree has exact (n - 1) edges.
        if (edges.length != (n - 1)) return false;

        // initialize
        for (int num_now = 0; num_now < n ;num_now++) {
            add(num_now);
        }

        // union
        for (int i = 0; i < edges.length ;i++) {
            int[] edge = edges[i];
            int num1 = edge[0];
            int num2 = edge[1];

            union(num1, num2);
        }

        // check if there are > 1 roots
        Integer root_prev = null;
        for (int num_now = 0; num_now < n ;num_now++) {
            Integer root = find_root(num_now);

            if (root_prev != null) {
                if (root_prev != root) {
                    return false;
                }
            }

            root_prev = root;
        }

        return true;
    }
}