Java solution using BFS


  • 0
    C
    public boolean validTree(int n, int[][] edges) {
            boolean[] visitedNodes = new boolean[n];
            Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
            
            for(int[] edge : edges){
                graph.computeIfAbsent(edge[0], v->new ArrayList<Integer>());
                graph.get(edge[0]).add(edge[1]);
                
                graph.computeIfAbsent(edge[1], v->new ArrayList<Integer>());
                graph.get(edge[1]).add(edge[0]);            
            }
            
            Queue<Integer> queue = new LinkedList<Integer>();
            queue.offer(0);
            
            while(!queue.isEmpty()){
                int top = queue.poll();
                
                // if a node is already visited then there is a cycle
                if(visitedNodes[top]){
                    return false;
                }
                
                visitedNodes[top] = true;
                
                // checks if a node is missing
                if(!graph.containsKey(top)){
                    continue;
                }
                
                // if there is a cycle then same node will be entered twice in the queue
                for(int node : graph.get(top)){
                    if(!visitedNodes[node]){
                        queue.offer(node);
                    }
                }
            }
            
            // checking for disjoint edge
            for(int i=0; i<visitedNodes.length; i++){
                if(!visitedNodes[i]){
                    return false;
                }
            }
            
            return true;
        }
    

Log in to reply
 

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