Course Schedule LeetCode solution in Java

1
class Solution {
2
  public boolean canFinish(int numCourses, int[][] prerequisites) {
3
    int n = numCourses;
4
    boolean[] visited = new boolean[n];
5
    boolean[] dfsVisited = new boolean[n];
6

7
    List<List<Integer>> adj = createAdjList(n, prerequisites);
8
    for (int i = 0; i < n; i++) {
9
      if (visited[i] == false) {
10
        if (isCycle(i, adj, visited, dfsVisited)) {
11
          return false;
12
        }
13
      }
14
    }
15
    return true;
16
  }
17

18
  // find cycle in a directed graph
19
  private boolean isCycle(int s, List<List<Integer>> adj, boolean[] visited, boolean[] dfsVisited) {
20

21
    visited[s] = true;
22
    dfsVisited[s] = true;
23

24
    for (int v : adj.get(s)) {
25
      if (visited[v] == false) {
26
        if (isCycle(v, adj, visited, dfsVisited)) {
27
          return true;
28
        }
29
      } else if (visited[v] == true && dfsVisited[v] == true) {
30
        return true;
31
      }
32
    }
33
    dfsVisited[s] = false;
34
    return false;
35
  }
36

37
  private List<List<Integer>> createAdjList(int n, int[][] prerequisites) {
38
    List<List<Integer>> adj = new ArrayList();
39

40
    for (int i = 0; i < n; i++) {
41
      adj.add(new ArrayList<>());
42
    }
43
    for (int[] e : prerequisites) {
44
      adj.get(e[1]).add(e[0]);
45
    }
46
    return adj;
47
  }
48
}