public class Solution {
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it‘s a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        // Write your code here
        //To find cycle and not connect node
        int nEdges = edges.length;
        //If total number of the node is n, for the tree(undirection graph), 
        //the number of the edges should be n - 1. 
        //If there are more than n - 1 edges, there are cycles.
        //If there are less than n - 1 edges, some nodes are not connected.
        if ( n != (nEdges + 1)) {
            return false;
        }
        //After the nEdge validation, we need to consider the on has cycles, 
        //but also contains un-fully-connected(which only have one or zero edge) nodes.
        //So we can create a hashset to remeber all the nodes that is connected.
        //And a Queue is also created to put the node that got connected.
        //If there are cycles and breaks, 
        //in the end the node which is not fully connected will not be able to add to the queue
        //In the end, we just need to compare the size of hashset with n. 
        HashMap<Integer, HashSet<Integer>> graph = initalizeGraph(n,edges); 
        HashSet<Integer> cnntNodes = new HashSet<Integer>();
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(0);
        cnntNodes.add(0);
        while (!queue.isEmpty()) {
            int curNode = queue.poll();
            HashSet<Integer> cnntToThisNode = graph.get(curNode);
            for (Integer i : cnntToThisNode) {
                if (cnntNodes.contains(i)) {
                    continue;
                }
                cnntNodes.add(i);
                queue.offer(i);
            }
        }
        return (cnntNodes.size() == n);
    }
    private HashMap<Integer, HashSet<Integer>> initalizeGraph(int n, int[][] edges) {
        HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new HashSet<Integer>());
        }
        
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        return graph;
    }
    
    
}