JAVA DFS beats 100%. Memorization to speed up performance


  • 0
    M

    Use a int type visited array to record the below states:
    0: This node has not been visited before
    1: This node is being visited currently
    2: This node has been visited, and proved to be good (no circle detected)

    Using this integer array of visited. One can combine "visiting" and "visited" together

       public boolean canFinish(int numCourses, int[][] prerequisites) {
            //Topological sort using DFS
            //Firset setup Graph using Ajacent List
            ArrayList<Integer> [] adjList = new ArrayList[numCourses]; //create adjacentlist and initiate
            for(int i=0; i< numCourses; i++){
                adjList[i]= new ArrayList<Integer>();
            }
            int[] degree = new int[numCourses]; // track indegree of each vertex
            Queue<Integer> queue = new LinkedList<Integer>(); //Queue to start BFS
            int count=0;
            for(int i=0; i< prerequisites.length; i++){
                adjList[prerequisites[i][1]].add(prerequisites[i][0]); // fill adjacentlist
                degree[prerequisites[i][0]]++;
            }
            
            //boolean[] visited = new boolean[numCourses];
            int []visited = new int[numCourses];// visited: 0 not visited, 1 visited 2 ; alreay cached
            for(int i=0; i<numCourses;i++){
                if(!dfsHelper(visited, adjList, i)) return false;
            }
            
            return true;
    }
    
     public boolean dfsHelper(int[] visited, List<Integer>[] adjList, int course){
            if(visited[course] ==1) return false;
            if(visited[course] ==2) return true;
            
            visited[course]= 1;
            for(int i=0; i< adjList[course].size();i++){
                if (!dfsHelper(visited, adjList, adjList[course].get(i))) return false;
            }
            
            visited[course]= 2; // Memorization + DFS  as usual technique to speed up performance
            return true;
        }
    
    
    
    
    
    

Log in to reply
 

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