# Java solution using Topological Sort: similar to alien dictionary

• ``````public class Solution {

public int[] findOrder(int numCourses, int[][] prerequisites) {

Map<Integer, Set<Integer>> graph = new HashMap<>();

//build graph
for(int[] edge : prerequisites) {
buildGraph(graph, edge[0], edge[1]);
}
for(int vertex = 0 ; vertex < numCourses; vertex++)
buildGraph(graph, vertex, -1);  // -1 indicates no edge

//perform topological sort
Set<Integer> visited = new HashSet<>();
Set<Integer> visiting = new HashSet<>();
Stack<Integer> res = new Stack<Integer>();
for(int node: graph.keySet()) {
if(visited.contains(node)) {
continue;
}
if(!DFS(graph, node, visited, visiting, res)) {
return new int[0];
}
}
int[] result = new int[numCourses];
for(int i = numCourses-1; i >= 0 && !res.isEmpty(); i--)
result[i] = res.pop();

return result;
}

public void buildGraph(Map<Integer, Set<Integer>> graph, int start, int end) {
graph.putIfAbsent(start, new HashSet<Integer>());
}

public boolean DFS(Map<Integer, Set<Integer>> graph, Integer root, Set<Integer> visited, Set<Integer> visiting, Stack<Integer> res) {
if(visiting.contains(root)) return false;

// Visit children first before visiting parent
Set<Integer> children = graph.get(root);
if(children != null) {
for(int child: children) {
if(visited.contains(child)) continue;
if(!DFS(graph, child, visited, visiting, res)) return false;
}
}

//now visit parent