Leetcode — topological sort

Leet code problems

• course schedule I: check cycle
• course schedule II: rearrange the course
• parallel courses: max depth

There are two ways of doing this (DFS, BFS). For both ways we have to first construct a graph:

ArrayList[] graph = new ArrayList[n];
for (int i=0;i<n;i++) {
  graph[i] = new ArrayList<Integer>();
}
for (int[] r : relation) {
  graph[r[0]].add(r[1]);
}

DFS

We maintain two arrays: visited & memo:

boolean[] visited = new boolean[n];
int[] memo = new int[n];

memo can be of type integer or boolean, it depends on the question and it’s similar to DP’s memorization.

Pseudo code:

We run dfs(node) for each node as a root, update max path where checking cycle at the same time.

func dfs(i) {
  if (memo[i] > 0) return memo[i];
  if (visited[i]) // has cycle;
  visited[i] = true;
  for (n : graph[i]) {
    memo[i] = Math.max(memo[i], dfs(n));
  }
  visited[i] = false; // this step is important to reset visited for    another path
  return memo[i];
}