My AC Answers: Union Find, BFS, DFS


  • 1
    Z
    // Union Find
    
    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            if(n < 1 || edges == null){
    			return false;
    		}
    		int[] uf = new int[n];
    		for(int i = 0; i < n; i++){
    			uf[i] = i;
    		}
    		for(int i = 0; i < edges.length; i++){
    			if(union(uf,edges[i][0],edges[i][1]) == false){
    				return false;
    			}
    		}
    		int count = 0;
    		for(int i = 0; i < n; i++){
    			if(uf[i] == i){
    				count++;
    			}
    		}
    		return count == 1;
        }
    	
    	public int find(int[] uf, int target){
    		int rst = target;
    		while(uf[rst] != rst){
    			rst = uf[rst];
    		}
    		// compress
    		int next = uf[target];
    		while(next != rst){
    			uf[target] = rst;
    			target = next;
    			next = uf[next];
    		}
    		return rst;
    	}
    	
    	public boolean union(int[] uf, int f1, int f2){
    		int p1 = find(uf,f1);
    		int p2 = find(uf,f2);
    		if(p1 == p2){
    			return false;
    		}
    		else{
    			uf[p1] = p2;
    		}
    		return true;
    	}
    	
    }
    
    // BFS
    
    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            if(n < 1 || edges == null){
    			return false;
    		}
    		ArrayList<Integer>[] edgeList = new ArrayList[n];
    		for(int i = 0; i < n; i++){
    			edgeList[i] = new ArrayList();
    		}
    		for(int[] edge : edges){
    			edgeList[edge[0]].add(edge[1]);
    			edgeList[edge[1]].add(edge[0]);
    		}
    		boolean[] visited = new boolean[n];
    
    		Queue<Integer> queue = new LinkedList();
    		queue.offer(0);
    		while(!queue.isEmpty()){
    			int top = queue.poll();
    			if(visited[top]){
    				return false;
    			}
    			visited[top] = true;
    			for(int next : edgeList[top]){
    				if(!visited[next]){
    					queue.offer(next);
    				}
    			}
    		}
    		for(boolean bl : visited){
    			if(!bl){
    				return false;
    			}
    		}
    		
    		return true;
        }
    }
    
    
    // DFS
    
    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            if(n < 1 || edges == null){
    			return false;
    		}
    		ArrayList<Integer>[] edgeList = new ArrayList[n];
    		for(int i = 0; i < n; i++){
    			edgeList[i] = new ArrayList();
    		}
    		for(int[] edge : edges){
    			edgeList[edge[0]].add(edge[1]);
    			edgeList[edge[1]].add(edge[0]);
    		}
    		boolean[] visited = new boolean[n];
    		if(dfs(edgeList,visited,0,0) == false){
    			return false;
    		}
    		for(boolean bl : visited){
    			if(!bl){
    				return false;
    			}
    		}
    		return true;
        }
    	
    	public boolean dfs(ArrayList<Integer>[] edgeList,boolean[] visited, int target,int father){
    		if(visited[target]){
    			return false;
    		}
    		visited[target] = true;
    		for(int next : edgeList[target]){
    			if(next != father){
    				if(dfs(edgeList,visited,next,target) == false){
    					return false;
    				}
    			}
    		}
    		return true;
    	}
    }
    
    

Log in to reply
 

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