Problem

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

思路

1. tree means number of edges == n - 1
2. via one node can reach anywhere in the graph
3. build the graph using list array
4. use bfs to traverse the graph

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

        List[] list = buildGraph(edges, n);
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> hash = new HashSet<>();
        queue.offer(0);
        hash.add(0);
        while (!queue.isEmpty()) {
            int curt = queue.poll();
            n--;
            List<Integer> neighbors = list[curt];
            for (Integer adj: neighbors) {
                if (hash.contains(adj)) continue;
                queue.offer(adj);
                hash.add(adj);
            }
        }
        return n == 0;
    }

    private List[] buildGraph(int[][] edges, int n) {
        List[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        for (int[] edge: edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        return graph;
    }