# My Java Solution, Typical Topology Ordering with comments

• ``````public class Solution {
public class Course implements Comparable<Course> {
int index;
ArrayList<Course> dependents;
int visitState; // -1 not visited, 0 visiting, 1: visited;
int topOrder; // Save Topology Order
public Course(int i) {
index = i;
dependents = new ArrayList<Course>();
visitState = -1;
topOrder = -1;
}
// Util functions
}

public ArrayList<Course> getDependents() {
return dependents;
}

public int getIndex() {
return index;
}

@Override
public int compareTo(Course otherCourse) {
return this.topOrder - otherCourse.topOrder;
}
}
public int[] findOrder(int numCourses, int[][] prerequisites) {
HashMap<Integer, Course> courses = new HashMap<Integer, Course>();
for(int i = 0; i < numCourses; i++) {
courses.put(i, new Course(i));
}

int m = prerequisites.length;
// Edge case
if (m == 0) {
int[] result = new int[numCourses];
for(int i = 0; i < numCourses; i++) {
result[i] = i;
}
return result;
}

// Normal Case: add prerequisites into Edges
for(int j = 0; j < m; j++) {
int preIndex = prerequisites[j][1];
int depIndex = prerequisites[j][0];
Course pre = courses.get(preIndex);
Course dep = courses.get(depIndex);
}

int[] availableOrder = new int[1];
availableOrder[0] = numCourses-1;
// Do topology ordering on the courses
while(findUnvisitedCourse(courses)!=null) {
boolean isValid = dfs(findUnvisitedCourse(courses), availableOrder);
if (!isValid) {
int[] emptyResult = new int[0];
return emptyResult;
}
}

ArrayList<Course> courseArray = new ArrayList<Course>(courses.values());
Collections.sort(courseArray);
int[] finalResult = new int[numCourses];
for(int i = 0; i < numCourses; i++) {
finalResult[i] = courseArray.get(i).getIndex();
}
return finalResult;
}

public Course findUnvisitedCourse(HashMap<Integer, Course> courses) {
ArrayList<Course> courseArray = new ArrayList<Course>(courses.values());
for(Course c: courseArray) {
if (c.visitState == -1) {
return c;
}
}
return null;
}

public boolean dfs(Course c, int[] availableOrder) {
// If the node is already visited, don't bother to loop deeper
if (c.visitState == 1) {
return true;
}
// If the node is undering exploring, it means a loop is formed and mark it false;
if (c.visitState == 0) {
return false;
}
// Start visiting the node
c.visitState = 0;
for(Course cc: c.getDependents()) {
boolean isValid = dfs(cc, availableOrder);
if (!isValid) return false;
}
// Done expoloring, mark it visited and give it the top order, available order --
c.visitState = 1;
c.topOrder = availableOrder[0];
availableOrder[0] = availableOrder[0] - 1;
return true;
}
}``````

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