DFS Solution in Java


  • 0
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
    		if(prerequisites==null || prerequisites.length==0) {
    			int[] a = new int[numCourses];
    			for(int i=0;i<numCourses;i++) {
    				a[i]=i;
    			}
    			return a;
    		}
    		Map<Integer,Set<Integer>> course2pres = new HashMap<Integer,Set<Integer>>();
    		for(int i=0;i<prerequisites.length;i++) {
    			if(course2pres.containsKey(prerequisites[i][0])) {
    				course2pres.get(prerequisites[i][0]).add(prerequisites[i][1]);
    			} else {
    				Set<Integer> pres = new HashSet<Integer>();
    				pres.add(prerequisites[i][1]);
    				course2pres.put(prerequisites[i][0], pres);
    			}
    		}
    		Set<Integer> coursesWithPre = course2pres.keySet();
    		boolean[] visited = new boolean[numCourses];
    		boolean[] visiting = new boolean[numCourses];
    		List<Integer> order = new ArrayList<Integer>();
    		for(int c: coursesWithPre) {
    			if(!visited[c]) {
    				if(!dfs(c,course2pres,visited,visiting,order))
    					return new int[0];
    			}
    		}
    		int[] arrayOrder = new int[numCourses];
    		Set<Integer> nopre = new HashSet<Integer>();
    		if(order.size()<numCourses) {
    			for(int i=0;i<numCourses;i++) {
    				if(!order.contains(i)) {
    					nopre.add(i);
    				}
    			}
    		}
    		order.addAll(nopre);
    		for(int i=0;i<arrayOrder.length;i++) {
    			arrayOrder[i] = order.get(i);
    		}
    		return arrayOrder;
    	}
    	public static boolean dfs(int c, Map<Integer,Set<Integer>> pres, boolean[] visited, boolean[] visiting, List<Integer> order) {
    		if(visiting[c]) return false;
    		visiting[c] = true;
    		if(pres.containsKey(c)) {
    			for(int i: pres.get(c)) {
    				if(!visited[i]) {
    					if(!dfs(i,pres,visited,visiting,order)) return false;
    				}
    			}
    		}
    		visiting[c] = false;
    		visited[c] = true;
    		order.add(c);
    		return true;
    	}

Log in to reply
 

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