Add a permanent visited to boost 107ms to 6ms, then why using topological Sort?


  • 0
    L

    I just cannot understand which problem is the type that we must implement topological sorting by using BFS. It seems every problem can be solved by using DFS efficiently, can any one help me?

    public boolean canFinish(int numCourses, int[][] prerequisites) {
            ArrayList[] graph = new ArrayList[numCourses];
            for(int i=0;i<numCourses;i++)
                graph[i] = new ArrayList();
                
            boolean[] visited = new boolean[numCourses];
            boolean[] reached = new boolean[numCourses];
            for(int i=0; i<prerequisites.length;i++){
                graph[prerequisites[i][1]].add(prerequisites[i][0]);
            }
    
            for(int i=0; i<numCourses; i++){
                if (reached[i]){
                    continue;
                }
                if(!dfs(graph,visited,i, reached))
                    return false;
            }
            return true;
        }
    
        private boolean dfs(ArrayList[] graph, boolean[] visited, int course, boolean[] reached){
            if(visited[course])
                return false;
            else
                visited[course] = true;
                reached[course] = true;
    
            for(int i=0; i<graph[course].size();i++){
                if(!dfs(graph,visited,(int)graph[course].get(i), reached))
                    return false;
            }
            visited[course] = false;
            return true;
        }
    

Log in to reply
 

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