Givennnodes labeled from0ton - 1and a list ofundirectededges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Notice

You can assume that no duplicate edges will appear in edges. Since all edges areundirected,[0, 1]is the same as[1, 0]and thus will not appear together in edges.

Have you met this question in a real interview?

Yes

Example

Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

1. BFS

need to store the graph in a HashMap<Integer, ArrayList<Integer>>() to store all the vertice and its neighbor.

two condition : 1.if there is n vertices, there must be n - 1 edge

1. all vertices are connect (through bfs from a vertice and see if all vertices can be reached)

public class Solution {
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
    /*union find*/
    /*
    public boolean validTree(int n, int[][] edges) {
        // Write your code here
        if (edges.length + 1 != n) {
            return false;
        }
        UF uf = new UF(n);
        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            int root_a = uf.find(a);
            int root_b = uf.find(b);
            if (root_a == root_b) {
                return false;
            }
            uf.union(a, b);
        }
        return true;
    }
    */
    public boolean validTree(int n, int[][] edges) {
        //check if the size satisfy n vertice, n - 1 edges
        if (edges.length + 1 != n) {
            return false;
        }

        HashMap<Integer, ArrayList<Integer>> graphMap = getGraph(n, edges);
        Queue<Integer> queue = new LinkedList<Integer>();
        HashSet<Integer> isVisited = new HashSet<>();

        queue.offer(0);
        isVisited.add(0);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (Integer neighbor : graphMap.get(cur)) {
                if (isVisited.contains(neighbor)) {
                    continue;
                }

                isVisited.add(neighbor);
                queue.offer(neighbor);
            }
        }
        return isVisited.size() == n; 

    }

    public HashMap<Integer, ArrayList<Integer>> getGraph(int n, int[][] edges) {
        HashMap<Integer, ArrayList<Integer>> ans = new HashMap<>();
        for (int i = 0; i < n; i++) {
            ans.put(i, new ArrayList<Integer>());
        }

        for (int i = 0; i < edges.length; i++) {
            int v = edges[i][0];
            int e = edges[i][1];
            ans.get(v).add(e);
            ans.get(e).add(v);
        }

        return ans;
    }


}