Java DFS+Recursion+Dynamic Programming


  • 0
    J
    public class Solution {
    	public boolean canFinish(int numCourses, int[][] prerequisites) {
    		
    		if(prerequisites.length == 0) return true;
    		
    		ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>(numCourses);
    		
    		for(int i = 0; i < numCourses; i++) graph.add(new ArrayList());
    		
    		for(int i = 0; i < prerequisites.length; i++) {
    			graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
    		}
    		
    		HashSet visited = new HashSet();
    		for(int i = 0; i < numCourses; i++) {
    			if(topo(i, graph, visited) == false) return false;
    			
    			graph.set(i, new ArrayList());
    			//graph.get(i).clear(); more efficient???
    		}
    		
    		return true;
    	}
    	
    	public boolean topo(int current, ArrayList<ArrayList<Integer>> graph, HashSet<Integer> visited) {
    		
    		if(visited.contains(current)) return false;
    		
    		if(graph.get(current).size() == 0) return true;
    		
    		for(Integer n : graph.get(current)) {
    			visited.add(current);
    			if(topo(n, graph, visited) == false) return false;
    			visited.remove(current);
    		}
    		
    		return true;
    	}
    }
    

Log in to reply
 

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