Cacher is the code snippet organizer for pro developers

class Solution {
    private int find(int[] parents, int i) {
        if (parents[i] == -1) {
            return i;
        }
        return find(parents, parents[i]);
    }
    public boolean validTree(int n, int[][] edges) {
        int[] parents = new int[n];
        Arrays.fill(parents, -1);
        
        for (int[] e : edges) {
            int a = find(parents, e[0]);
            int b = find(parents, e[1]);
            if (a == b) return false;
            //union
            parents[a] = b;
        }
        return edges.length == n - 1;
    }
    
}

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // initialize adjacency list
        List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);
        
        // initialize vertices
        for (int i = 0; i < n; i++)
            adjList.add(i, new ArrayList<Integer>());
        
        // add edges    
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0], v = edges[i][1];
            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }
        
        boolean[] visited = new boolean[n];
        
        // make sure there's no cycle
        if (hasCycle(adjList, 0, visited, -1))
            return false;
        
        // make sure all vertices are connected
        for (int i = 0; i < n; i++) {
            if (!visited[i]) 
                return false;
        }
        
        return true;
    }
    
    // check if an undirected graph has cycle started from vertex u
    boolean hasCycle(List<List<Integer>> adjList, int u, boolean[] visited, int parent) {
        visited[u] = true;
        
        for (int i = 0; i < adjList.get(u).size(); i++) {
            int v = adjList.get(u).get(i);
            
            if ((visited[v] && parent != v) || (!visited[v] && hasCycle(adjList, v, visited, u)))
                return true;
        }
        
        return false;
    }
}

/*
To tell whether a graph is a valid tree, we have to:

Make sure there is no cycle in the graph - this has to be a none-cyclic graph;
Make sure every node is reached - this has to be a connected graph;

*/

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);
        for(int i = 0; i < n; i++){
            adjList.add(new ArrayList<Integer>());
        }
        
        for(int i = 0; i < edges.length; i++){
            int start = edges[i][0];
            int end = edges[i][1];
            adjList.get(start).add(end);
            adjList.get(end).add(start);
        }
        
        boolean[] explored = new boolean[n];
        
        if(hasCycle(adjList, 0, explored)) return false;
        for(boolean i : explored){
            if (!i){
                return false;
            }
        }
        return true;
    }
    
    
    public boolean hasCycle(List<List<Integer>> adjList, int root, boolean[] explored){
        
        Queue<Integer> frontier = new LinkedList<Integer>();
        frontier.add(root);
        
        while(!frontier.isEmpty()){
            int node = frontier.poll();
            if( !explored[node]){
                for(int i = 0; i < adjList.get(node).size(); i++){
                    if(!explored[adjList.get(node).get(i)]) {
                        frontier.add(adjList.get(node).get(i));
                    }
                }
            } else {
                return true;
            }
            explored[node] = true;
        }
        return false;
    }
}