Java Solution Using DFS


  • 0
    C
       //I Used three different notations not visited(0) , visited(1),finished(2) for each subject
        
        import java.util.Arrays;
        public class Solution {
             boolean result=true;
             public boolean canFinish(int numCourses, int[][] prerequisites) {
                if(numCourses == 0 || prerequisites.length == 0) return true;
                int[] visited = new int[numCourses];
                List<List<Integer>> courses = new ArrayList<List<Integer>>(numCourses);
                for(int i=0;i<numCourses;i++)
                courses.add(new ArrayList<Integer>());
                for(int i=0;i<prerequisites.length;i++)
                courses.get(prerequisites[i][0]).add(prerequisites[i][1]);
                for(int i=0;i<numCourses;i++)
                {
                    if(!courses.get(i).isEmpty() && visited[i]==0)
                    {
                    visited[i]=1;
                    dfs(i,courses.get(i),courses,visited);
                    }
                    else
                    visited[i]=2;
                    
                }
                return result;
            }
            
            private void dfs(int i,List<Integer> courselist,List<List<Integer>> courses,int[] visited)
            {
                if(!courselist.isEmpty())
                {
                for(int j:courselist)
                {
                    if(visited[j]==0)
                    {
                       visited[j]=1;
                       dfs(j,courses.get(j),courses,visited);
                    }
                   else if(visited[j]==2)
                   {
                       visited[i]=2;
                   }
                   else if(visited[j]==1)
                   {
                       result=false;
                       return;
                   }
                }
                visited[i]=2;
                }
                else
                visited[i]=2;
            }
        }

Log in to reply
 

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