```
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses <= 1) return true;
List<List<Integer>> adjs = new ArrayList<>();
boolean[] visited = new boolean[numCourses];
while (numCourses-- > 0) adjs.add(new ArrayList<>());
for (int[] edge : prerequisites) adjs.get(edge[0]).add(edge[1]);
return !hasCycle(adjs, visited);
}
private boolean hasCycle(List<List<Integer>> adjs, boolean[] visited) {
boolean[] onStack = new boolean[visited.length];
for (int i = 0; i < visited.length; i++) {
if (visited[i] == false) {
if (dfs(i, adjs, visited, onStack) == true) return true;
}
}
return false;
}
private boolean dfs(int node, List<List<Integer>> adjs, boolean[] visited, boolean[] onStack) {
visited[node] = true; onStack[node] = true;
for (int to : adjs.get(node)) {
if (visited[to] == false) {
if (dfs(to, adjs, visited, onStack) == true) return true;
} else if (onStack[to] == true) {
return true;
}
}
onStack[node] = false;
return false;
}
}
```

This question immediately reads as a question to detect cycles in a directed graph

- convert it to directed graph
- detect directed cycles

Another way is to use incoming and outgoing edges. More on this in a post I wrote for the follow-up question.

**More on onStack array:**

onStack is set to true when we first visit it and it is set to false after we have explored all the outgoing edges.

The way to think about how it detects directed cycles proceeds like this. If a directed graph has a cycle, it must mean that one of the nodes in the cycle must have an outgoing path that leads back to itself. The *for* loop in *dfs* method explores all outgoing paths from a node. This node is on a cycle if a successive *dfs* call finds a path back to the current node.

On the other hand, if all edges are explored and no returning paths are found, this node is not on a cycle. Hence, we only set onStack to be false after the *for* loop.