261. Graph Valid Tree

// Some code
class Solution {
    int[] graph;
    int[] size;
    int count;
    boolean hasCircle;
    public boolean validTree(int n, int[][] edges) {
        graph = new int[n];
        size = new int[n];
        for(int i=0; i<graph.length; i++){
            graph[i]=i;
            size[i]=1;
        }
        count = n;
        
        for(int[] edge : edges){
            union(edge[0], edge[1]);
        }
        
        return !hasCircle && count==1;
    }
    private void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP != rootQ){
            if(size[rootP]>size[rootQ]){
                graph[rootQ] = rootP;
                size[rootP]+=size[rootQ];
            }else{
                graph[rootP]=rootQ;
                size[rootQ]+=size[rootP];
            }
            count--;
        }else{
            hasCircle=true;
        }
    }
    private int find(int p){
        while(graph[p] != p){
            graph[p]=graph[graph[p]];
            p=graph[p];
        }
        return p;
    }
}

// Some code

class Solution {
    boolean[] visited;
    boolean[] onPath;
    boolean containCircle;
    public boolean validTree(int n, int[][] edges) {
        visited = new boolean[n];
        onPath = new boolean[n];
        List<Integer>[] graph = buildGraph(edges, n);
        for(int i=0; i<graph.length; i++){
            if(!visited[i]){
                traverse(graph, i, -1);
            }
        }
        return !containCircle && n-1==edges.length;
    }

    private void traverse(List<Integer>[] graph, int curr, int prev){
        if(containCircle) return;
        visited[curr]=true;
        
        onPath[curr]=true;
        for(int next : graph[curr]){
            if(next!=prev){
                if(onPath[next]){
                    containCircle=true;
                }else{
                    traverse(graph, next, curr);
                }
            }
        }
        onPath[curr] = false;
    }
    
    private List<Integer>[] buildGraph(int[][] edges, int n){
        List<Integer>[] graph = new LinkedList[n];
        for(int i=0; i<n; i++){
            graph[i]=new LinkedList<>();
        }
        
        for(int[] edge : edges){
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        
        return graph;
    }
    
}