# JAVA topological sort solution with DFS and Stack

• ``````public class Solution {

private Stack<Integer> stack = new Stack<Integer>();
private ArrayList<ArrayList<Integer>> x = new ArrayList<ArrayList<Integer>>();

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

for(int i = 0; i < numCourses; i++)
{
}

for(int j = 0; j < prerequisites.length; j++)
{
int f = prerequisites[j][0];
int s = prerequisites[j][1];

}

boolean[] visited = new boolean[numCourses];

for(int i = 0; i < numCourses; i++)
{
if(!visited[i])
{
boolean result = dfsWithCycle(i, new ArrayList<Integer>(), visited);
if(!result)
{
return new int[0];
}
}
}

int[] finalOrder = new int[numCourses];

for(int i = 0; i < numCourses; i++)
{
finalOrder[i] = stack.pop();
}

return finalOrder;

}

public boolean dfsWithCycle(int v, ArrayList<Integer> prefix, boolean[] visited)
{
for(int i = 0; i < x.get(v).size(); i++)
{
if(!(prefix.contains(x.get(v).get(i))))
{
if(!visited[x.get(v).get(i)])
{
ArrayList<Integer> newPrefix = new ArrayList<Integer>();

boolean a = dfsWithCycle(x.get(v).get(i), newPrefix, visited);

if(!a)
{
return a;
}
}
}
else
{
return false;
}
}

visited[v] = true;
stack.push(v);

return true;
}
}``````

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