My BFS Solution


  • 2
    B
    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            
            // Create an adj list 
            List<List<Integer>> adjList = new ArrayList<List<Integer>>();
            for (int i = 0; i < n; i++) {
                adjList.add(new ArrayList<Integer>());
            }
            
            for (int[] edge : edges) {
                adjList.get(edge[1]).add(edge[0]);
                adjList.get(edge[0]).add(edge[1]);
            }
            
            boolean[] visited = new boolean[n];
            
            Queue<Integer> queue = new LinkedList<Integer>();
            queue.offer(0);
            int parent = -1;
            
            while (!queue.isEmpty()) {
                int vertexId = queue.poll();
                
                if (visited[vertexId]) {
                    return false;
                }
                
                visited[vertexId] = true;
                
                for (int neighbor : adjList.get(vertexId)) {
                    if (!visited[neighbor]) {
                        queue.offer(neighbor);
                    }
                }
                
                parent = vertexId;
            }
            
            // Check the islands
            for (boolean v : visited) {
                if (!v) {
                    return false;
                }
            }
            
            return true;
        }
    }

Log in to reply
 

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