Leetcode 261 Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Solution 1: Build the Graph then DFS

 public class Solution {  
   public boolean validTree(int n, int[][] edges) {  
     List<Integer>[] adj=new List[n];  
     for (int i=0; i<n; i++) adj[i]=new LinkedList<>();  
     for (int i=0; i<edges.length; i++) {  
       adj[edges[i][0]].add(edges[i][1]);  
       adj[edges[i][1]].add(edges[i][0]);  
     }  
     boolean[] marked=new boolean[n];  
     boolean[] hasCycle=new boolean[1];  
     dfs(adj,-1,0,hasCycle,marked);  
     for (int v=0; v<n; v++) {  
       if (!marked[v]) return false;  
     }  
     return !hasCycle[0];  
   }  
   private void dfs(List<Integer>[] adj, int s, int v, boolean[] hasCycle, boolean[] marked) {  
     marked[v]=true;  
     for (int w: adj[v]) {  
       if (hasCycle[0]) return;  
       else if (w!=s) {  
         if (!marked[w]) dfs(adj,v,w,hasCycle,marked);  
         else hasCycle[0]=true;  
       }  
     }  
   }  
 }  

Solution 2: Uni-Find

 public class Solution {  
   public boolean validTree(int n, int[][] edges) {  
     int[] nums=new int[n];  
     Arrays.fill(nums,-1);  
     for (int[] edge: edges) { //check loop  
       int x=edge[0], y=edge[1];  
       int c1=0, c2=0;  
       while (nums[x]!=-1) {  
         x=nums[x];  
         c1++;  
       }  
       while (nums[y]!=-1) {  
         y=nums[y];  
         c2++;  
       }  
       if (x==y) return false;  
       if (c1>c2) nums[y]=x;//connected small part to big part  
       else nums[x]=y;  
     }  
     int count=0; //check all connected, nums of -1 is nums of cc  
     for (int i=0; i<n; i++) {  
       if (nums[i]==-1 && ++count>1) return false;  
     }  
     return true;  
   }  
 }