# AC modular Java solution

• We just need to detect if there's any cycle in the directed graph, I've encapsulated the core functions in a Graph class:

``````public class Solution {

public boolean canFinish(int numCourses, int[][] prerequisites) {
Graph graph = new Graph(numCourses);

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

return !graph.isCyclic();
}

// ---------------------
//  Directed Graph
// ---------------------
class Graph {
int n;          // number of vertex

Graph(int x) {
n = x;
matrix = new int[n][n];
}

void addEdge(int u, int v) {
matrix[u][v] = 1;
}

// check if there's a cycle in the graph
boolean isCyclic() {
boolean[] visited = new boolean[n];
boolean[] stack = new boolean[n];

for (int u = 0; u < n; u++)
if (dfs(u, visited, stack))
return true;

return false;
}

boolean dfs(int u, boolean[] visited, boolean[] stack) {
// mark it as visited
visited[u] = true;
stack[u] = true;

// check all its neighbors
for (int v = 0; v < n; v++)
if (matrix[u][v] > 0)
if (stack[v] == true || (visited[v] == false && dfs(v, visited, stack)))
return true;

// remove the vertex from recursion stack
stack[u] = false;

return false;
}
}

}``````

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