# Java DFS (V + E) running time clear solution.

• Here is a solution inspired by the Coursera Algorithms, Part II code.

It's running time is O(V + E) and it uses O(V * degree(V)) additional memory for graph representation and also O(V) for the marking the visited nodes.

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if(numCourses <= 0) {
return false;
}

// builds the graph out of the adjacency matrix
final Digraph coursers = new Digraph(numCourses);

for(int i = 0; i < prerequisites.length; i++) {

}

final Cycle cycle = new Cycle(coursers);
return !cycle.hasCycle();
}

private static class Digraph {

private final int V;

@SuppressWarnings("unchecked")
public Digraph(int V) {
this.V = V;
for(int ind = 0; ind < V; ind++) {
}
}

public int V() {
return V;
}

public void addEdge(int v, int w) {

}

}
}

private static class Cycle {

private final Digraph graph;
private final boolean[] marked;
private final boolean[] stack;
private boolean hasCycle;

public Cycle(Digraph graph) {
this.graph = graph;

marked = new boolean[graph.V()];
stack = new boolean[graph.V()];
for(int v = 0; v < graph.V(); v++) {
if(!marked[v]) {
dfs(v);
}
}
}

private void dfs(int v) {
marked[v] = true;
stack[v] = true;

if(hasCycle) {
return;
} else if(stack[w]) {
hasCycle = true;
} else if(!marked[w]) {
dfs(w);
}
}
stack[v] = false;
}

public boolean hasCycle() {
return hasCycle;
}
}
}``````

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