# 5ms DFS beat 98% and 9ms BFS in java

• DFS:

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList<Integer>[] graph = new ArrayList[numCourses];//tricky
for(int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<Integer>();
}

for(int[] pre : prerequisites) {
}

boolean[] visited = new boolean[numCourses],
boolean[] finished = new boolean[numCourses];
for(int i = 0; i < numCourses; i++) {
if(!helper(graph, visited, finished, i)){
return false;
}
}

return true;
}

public boolean helper(ArrayList[] graph, boolean[] visited, boolean[] finished, int s) {
if(finished[s]) {
return true;
} else if(visited[s]) {
return false;
} else {
visited[s] = true;
}

for(int i=0; i<graph[s].size();i++){
return false;
}
}

finished[s] = true;
return true;
}
}
``````

BFS:

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for(int i = 0; i < numCourses; i++) {
}

int[] indegree = new int[numCourses];
for(int[] edge : prerequisites) {

indegree[edge[0]]++;
}

for(int i = 0; i < numCourses; i++) {
if(indegree[i] == 0){
q.offer(i);
}
}

int count = 0;
while(!q.isEmpty()) {
int s = q.poll();
count++;
}
}
}

return count == prerequisites.length;
}
}
``````

• Thanks for the solution. Similar idea. I just tried to make it more concise.
Basically state is an int array that mimics visited (1) and finished (2).

``````class Solution {
public boolean canFinish(int num, int[][] preReqs) {
for (int i = 0; i < adj.length; i++) adj[i] = new ArrayList<>();

for (int[] edge : preReqs) {
int from = edge[1], to = edge[0];
}

int[] state = new int[num];
for (int i = 0; i < num; i++) {
if (!dfs(adj, state, i)) return false;
}

return true;
}

boolean dfs(List<Integer>[] adj, int[] state, int e) {
if (state[e] == 2) return true;
if (state[e] == 1) return false;
state[e] = 1;

for (int next : adj[e]) {
if (!dfs(adj, state, next)) return false;
}

state[e] = 2;
return true;
}
}
``````

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