# Detailed Comment on DFS solution for Course Schedule I & II

• For the DFS part, I can understand now. Thanks for sharing! For more details, please refer to classic CLRS.

The 0, 1, 2 in visited array corresponds to White, Gray, Black in CLRS. As CLRS says, The key idea is that when we first explore an edge, the color of vertex tells us something about the edge:

1. WHITE (vis[nb] == 0) indicates a tree edge,
2. GRAY (vis[nb] == 1) indicates a back edge, and
3. BLACK (vis[nb] == 2) indicates a forward or cross edge.
``````    public boolean canFinish(int n, int[][] prereq) {
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();

int[] vis = new int[n];     // reuse so that each node visited once
for (int i = 0; i < n; i++) // must check every node. eg.[1,0],[0,1]
if (dfs(adj, i, vis)) return false;
return true;
}

// Check if back edge (directed cycle) exists. If not => DAG => able to topo sort
private boolean dfs(List<Integer>[] adj, int v, int[] vis) {
vis[v] = 1;
for (int nb : adj[v]) {
if (vis[nb] == 1) return true; // visited and nb is v's ancestor => back edge
if (vis[nb] == 0 && dfs(adj, nb, vis)) return true; // nb is not visited => tree edge
// else vis[nb]==2, nb is visited but not ancestor => forward or cross edge
}
vis[v] = 2;
return false;
}
``````

The illustration below is an example. F for forward edge, C for cross edge, B for back edge.

Using same idea, we can solve Course Schedule II in DFS manner as well. The key note is Topo-sort order is the reverse order of their finish time.

``````    public int[] findOrder(int n, int[][] prereq) {
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();

int[] vis = new int[n];
for (int i = 0; i < n; i++)
if (vis[i] == 0 && dfs(ret, adj, i, vis)) return new int[0];
return ret.stream().mapToInt(i -> i).toArray();
}

vis[v] = 1;
for (int nb : adj[v]) {
if (vis[nb] == 1) return true;
if (vis[nb] == 0 && dfs(ret, adj, nb, vis)) return true;
}
vis[v] = 2;
ret.addFirst(v); // Topo-sort order is the reverse order of their finish time
return false;
}
``````

• Nice, but it seems I can't initialize the adjacency list as you did `List<Integer>[] adj = new List[n];` in eclipse. How come?
Update: It's just a warning, but still don't understand why it can be like this: `Type safety: The expression of type List[] needs unchecked conversion to conform to List<Integer>[]`

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