Java solution based on detecting cycle in a graph.

  • 0
    import java.util.*;
    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Graph g = new Graph(numCourses);
            int rowl = prerequisites.length;
            for(int i=0;i<rowl;i++)
                    g.addEdge(prerequisites[i][0], prerequisites[i][1]);
                boolean[] visited = new boolean[numCourses];
                boolean[] recstack = new boolean[numCourses];
                for(int i = 0; i < numCourses; i++){
                    visited[i] = false;
                    recstack[i] = false;
               for(int i = 0; i < numCourses; i++)
                    if (!isCyclicUtil(i, visited, recstack, g))
                        return false;
            return true;
        public boolean isCyclicUtil(int vertex, boolean[] visited, boolean[] recstack, Graph g){
            if(visited[vertex] == false){
                recstack[vertex] = true;
                Iterator<Integer> i = g.adj[vertex].listIterator();
                    int n =;
                    if(!visited[n] && !isCyclicUtil(n,visited, recstack, g))
                        return false;
                   else if(recstack[n])
                        return false;
            recstack[vertex] = false;
            return true;
    class Graph{
        public int V;
        public LinkedList<Integer> adj[];
        public Graph(int v){
            V = v;
            adj = new LinkedList[v];
            for(int i=0;i<v;i++)
                adj[i] = new LinkedList();
        public void addEdge(int u, int v){

Log in to reply

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