Java DFS, beats 90%, 7ms


  • 0
    V
        int[] numArr;
        ArrayList<Integer>[] myGraph;
        boolean isCir;
        public boolean canFinish(int numCourses, int[][] prereq) 
        {
            if(numCourses == 0 || prereq == null || prereq.length == 0 || prereq[0].length == 0)
                return true;
            numArr = new int[numCourses];
            myGraph = new ArrayList[numCourses];
            for(int i = 0; i < prereq.length; i++)
            {
                ArrayList<Integer> tempList;
                if(myGraph[prereq[i][0]] == null)
                    tempList = new ArrayList<Integer>();
                else
                    tempList = myGraph[prereq[i][0]];
                tempList.add(prereq[i][1]);
                myGraph[prereq[i][0]] = tempList;
            }
            for(int i = 0; i < numCourses && !isCir; i++)
            {
                if(numArr[i] == 0)
                    dfs(i);
            }
            return !isCir;
        }
        void dfs(int n)
        {
            if(numArr[n] == 2)
                return;
            if(numArr[n] == 1)
            {
                isCir = true;
                return;
            }
            numArr[n] = 1;
            List<Integer> myG = myGraph[n];
            if(myG != null && myG.size() > 0)
                for(int i: myG)
                    dfs(i);
            numArr[n] = 2;
        }

Log in to reply
 

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