# Java DFS - typical topological sort

• ``````class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
// algorithm 2017/08/27: DFS to track the order how we decide whether a course has no other dependency (and no cycle)

if (null == prerequisites || 0 == numCourses) {
return new int[0];
}

// assemble inDegrees, and use a hashMap to track dependency
HashMap<Integer, Set<Integer>> dependencies = new HashMap<>();
for (int[] prerequisite : prerequisites) {
Set<Integer> dependsOn = dependencies.get(prerequisite[0]);
if (null == dependsOn) {
dependsOn = new HashSet<>();
dependencies.put(prerequisite[0], dependsOn);
}
}

int[] decidedResult  = new int[numCourses];  // 0: not decided, 1: has no cycle; 2: has cycle
List<Integer> orders = new ArrayList<>();
boolean hasCycle     = false;
for (int course = 0; course < numCourses; course++) {
boolean[] visited = new boolean[numCourses];        // track visisted nodes
if (findCycle(dependencies, decidedResult, visited, orders, course)) {
hasCycle = true;
break;  // find a cycle, no need to continue
}
}

if (hasCycle) {
return new int[0];
} else {
int[] result = new int[numCourses];
int index    = 0;
for (int course : orders) {
result[index++] = course;
}
return result;
}

}

private boolean findCycle(HashMap<Integer, Set<Integer>> dependencies, int[] decidedResult, boolean[] visited, List<Integer> orders, int fromCourse) {
if (1 == decidedResult[fromCourse]) {
return false;        // there is no cycle
} else if (2 == decidedResult[fromCourse]) {
return true;       // there is a cycle
}

if (visited[fromCourse]) {
decidedResult[fromCourse] = 2;
return true;        // there is a cycle
}
visited[fromCourse] = true;

// follow all dependencies in a DFS fashion
Set<Integer> dependsOn = dependencies.get(fromCourse);
if (null != dependsOn) {
for (int dependOn : dependsOn) {
if (findCycle(dependencies, decidedResult, visited, orders, dependOn)) {
decidedResult[fromCourse] = 2;
return true;
}
}
}
visited[fromCourse] = false;
// no cycle after checking all dependencies
decidedResult[fromCourse] = 1;