# 5ms Elegant Java DFS + BFS Toposort, Beats 98%!

• DFS

``````    public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] matrix = new List[numCourses];
int[] visited = new int[numCourses];

// initialize adjacency list and indegree list
for(int i=0; i<prerequisites.length; i++) {
int[] edge = prerequisites[i];
if (matrix[edge[1]] == null) {
matrix[edge[1]] = new ArrayList();
}
}

for(int i=0; i<numCourses; i++) {
if (visited[i] == 0) { // only visit unvisited nodes
if(!dfs(matrix, visited, i)) return false;
}
}

return true;
}

public boolean dfs(List<Integer>[] matrix, int[] visited, int i) {
if (visited[i] == 1) return false; // cycle detected
if (visited[i] == 2) return true; // if fully visited, there is no chance for cycle
if (matrix[i] == null) { // no outgoing edges, so we can say it is fully visited
visited[i] = 2;
return true;
}

visited[i] = 1; // temp mark, signifys visited on same path, used for cycle detection
for(Integer adj : matrix[i]) { // dfs step
if (!dfs(matrix, visited, adj)) return false;
}

visited[i] = 2; // permanent mark, fully visited all children
return true;
}
``````

For fun, here is 9ms BFS solution

``````    public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] matrix = new List[numCourses];
int[] indegree = new int[numCourses];
int count = 0;

//build graph representation as adjacency list
for(int i=0; i<prerequisites.length; i++) {
int[] edge = prerequisites[i];
if (matrix[edge[1]] == null) {
matrix[edge[1]] = new ArrayList();
}

indegree[edge[0]]++;
}

// add all nodes that have 0 pre-reqs as start points
for(int i=0; i<numCourses; i++) {
if (indegree[i] == 0) {
}
}

while(!q.isEmpty()) {
int cur = q.poll();
count++; // if we have entered the while loop, we know cur has had its pre-reqs already visited, so safe to increment count (or even add to topological ordering) here
if (matrix[cur] == null) continue; // no out edges
if (--indegree[adj] == 0) { // only add to queue when indegree reaches 0, that way we know all prereqs have been fulfilled