LeetCode 261. Graph Valid Tree

Question

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.

Explanation

构造图的时候，用Hashmap这个数据结构存邻居。之后再去遍历邻居。图是树的条件有两个：1. 有n-1条边。2. 每个点都能联通。

Code

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // Condition 1: n-1 edges
        // Condition 2: n个点联通

        if (edges == null) return false;
        if (edges.length != n-1 ) return false;
        HashMap<Integer, Set<Integer>> graph = initialGraph (n,edges);
        Set<Integer> set = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        // bfs
        queue.offer(0);
        set.add(0);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for(Integer neighbour:graph.get(node)) {
                if (set.contains(neighbour)) {
                    continue;
                } else {
                    set.add(neighbour);
                    queue.offer(neighbour);
                }
            }
        }

        return set.size() == n;

  

    }

    public HashMap<Integer, Set<Integer>> initialGraph (int n, int[][] edges) {
        HashMap<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i=0; i<n; i++) {
            Set<Integer> set = new HashSet<>();
            graph.put(i, set);
        }
        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;


    }
}