Java solution based on detecting cycle in a graph.


  • 0
    D
    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){
                visited[vertex]=true;
                recstack[vertex] = true;
                
                Iterator<Integer> i = g.adj[vertex].listIterator();
                
                while(i.hasNext()){
                    int n = i.next();
                    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){
            adj[u].add(v);
        }
    }
    

Log in to reply
 

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