O(|V|+|E|)=O(|V|)=O(|E|) java solution using BFS


  • 0
    L
    public boolean validTree(int n, int[][] edges) {
        if(edges.length!=n-1) return false; 
        
        // construct adjacency list
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        for(int [] edge: edges) {
            if(!map.containsKey(edge[0])) map.put(edge[0], new ArrayList<Integer>());
            map.get(edge[0]).add(edge[1]);
            if(!map.containsKey(edge[1])) map.put(edge[1], new ArrayList<Integer>());
            map.get(edge[1]).add(edge[0]);
        }
    
        // traverse from any node, here start from node 0
        HashSet<Integer> visited = new HashSet<Integer>();
        LinkedList<Integer> queue = new LinkedList<Integer>();
        visited.add(0);
        queue.offer(0);
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            if(map.containsKey(cur)) {
                for(Integer neighbor:map.get(cur)) {
                    if(!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
            }
        }
        
        return visited.size()==n;
    }

  • 0
    B

    I may be wrong, but isn't this a BFS ?


  • 0
    L

    You are right :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.