Course Schedule 2 - Get Ordered Courses

Input: numCourses = 2, prerequisites =[[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Input: numCourses = 4, prerequisites =[[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Input: numCourses = 1, prerequisites = []
Output: [0]

public int[] findOrder(int numCourses, int[][] prerequisites) {
	if (prerequisites == null) {
		throw new IllegalArgumentException("illegal prerequisites array");
	}

	int len = prerequisites.length;

	//if there is no prerequisites, return a sequence of courses
	if (len == 0) {
		int[] res = new int[numCourses];
		for (int m = 0; m<numCourses; m++) {
			res[m] = m;
		}
		return res;
	}

	//records the number of prerequisites each course (0,...,numCourses-1) requires
	int[] pCounter = new int[numCourses];
	for (int i = 0; i<len; i++) {
		pCounter[prerequisites[i][0]]++;
	}

	//stores courses that have no prerequisites
	LinkedList<Integer> queue = new LinkedList<Integer> ();
	for (int i = 0; i<numCourses; i++) {
		if (pCounter[i] == 0) {
			queue.add(i);
		}
	}

	int numNoPre = queue.size();

	//initialize result
	int[] result = new int[numCourses];
	int j = 0;

	while (!queue.isEmpty()) {
		int c = queue.remove();
		result[j++] = c;

		for (int i = 0; i<len; i++) {
			if (prerequisites[i][1] == c) {
				pCounter[prerequisites[i][0]]--;
				if (pCounter[prerequisites[i][0]] == 0) {
					queue.add(prerequisites[i][0]);
					numNoPre++;
				}
			}

		}
	}

	//return result
	if (numNoPre == numCourses) {
		return result;
	} else {
		return new int[0];
	}
}

public int[] findOrder(int numCourses, int[][] prerequisites) {
	int len = prerequisites.length;
	// course directed graph
	Map<Integer, Set<Integer>> graph = new HashMap<>();
	for(int i = 0; i < numCourses; i++){
		graph.put(i, new HashSet<>());
	}
	for (int[] courseDep: prerequisites){
		int crs = courseDep[0];
		int pre = courseDep[1];
		graph.get(crs).add(pre);
	}

	Set<Integer> visiting = new HashSet<>();
	Set<Integer> visited = new LinkedHashSet<>();// we care about order as well
	for (int i = 0; i<numCourses; i++){
		if(!dfs(i, graph, visiting, visited)){
			return new int[0];
		}
	}
	
	int[] ans = new int[visited.size()];
	int i = 0;
	for (int num : visited) {
	      ans[i++] = num;
	}
	return ans;
}

public boolean dfs(int crs, Map<Integer, Set<Integer>> graph, Set<Integer> visiting, Set<Integer> visited){
	// we are still visiting, but we find it again
	if(visiting.contains(crs)){
		return false;
	}
	
	if(visited.contains(crs)){
		return true;
	}
	
	visiting.add(crs);
	for(int pre: graph.get(crs)){
		// if returns false, that means a cycle
		if(!dfs(pre, graph, visiting, visited)){
			return false;
		}
	}
	// no cycle encountered from crs as starting node
	visiting.remove(crs);
	visited.add(crs);
	return true;
}