class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
final int[] res = new int[numCourses];
if (numCourses == 0) {
return res;
}
if (prerequisites.length == 0) {
for (int i = 0; i < numCourses; i++) {
res[i] = i;
}
return res;
}
final Stack<Integer> stack = new Stack<>();
final Map<Integer, Set<Integer>> graph = new HashMap<>();
final Map<Integer, Integer> indegree = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
graph.put(i, new HashSet<>());
indegree.put(i, 0);
}
for (final int[] edge : prerequisites) {
graph.get(edge[0]).add(edge[1]);
indegree.merge(edge[1], 1, Integer::sum);
}
final Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree.get(i) == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
final int front = queue.poll();
stack.push(front);
for (final int adj : graph.get(front)) {
indegree.merge(adj, -1, Integer::sum);
if (indegree.get(adj) == 0) {
queue.offer(adj);
}
}
}
for (int i = 0; i < numCourses; i++) {
if (indegree.get(i) != 0 ){
return new int[0];
}
}
for (int i = 0; i < numCourses; i++) {
res[i] = stack.pop();
}
return res;
}
}
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
final int[] res = new int[numCourses];
if (numCourses == 0) return res;
if (prerequisites.length == 0) {
for (int i = 0; i < numCourses; i++) res[i] = i;
return res;
}
final Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < numCourses; i++) graph.put(i, new HashSet<>());
for (final int[] edge: prerequisites) graph.get(edge[0]).add(edge[1]);
final Queue<Integer> queue = new LinkedList<>();
final int[] visited = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0) {
if (dfsTopoSort(i, graph, visited, queue)) {
return new int[0];
}
}
}
for (int i = 0; i < numCourses; i++) {
res[i] = queue.poll();
}
return res;
}
private boolean dfsTopoSort(final int v, final Map<Integer, Set<Integer>> graph, final int[] visited, final Queue<Integer> queue) {
if (visited[v] == -1) return true;
if (visited[v] == 1) return false;
visited[v] = -1;
for (final int adj : graph.get(v)) {
if (dfsTopoSort(adj, graph, visited, queue)) {
return true;
}
}
visited[v] = 1;
queue.offer(v);
return false;
}
}