5ms - 97% - Topo Traverse


  • 1
    O
    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            List<Integer>[] nb = new List[numCourses];
            for (int[] e : prerequisites) {
                if (nb[e[1]] == null) nb[e[1]] = new ArrayList();
                nb[e[1]].add(e[0]);
            }
            boolean[] visiting = new boolean[numCourses], visited = new boolean[numCourses];
            
            for (int i = 0; i < numCourses; i++)
                if (!visited[i] && !dfs(i, visited, visiting, nb)) return false;
            
            return true;
        }
        
        private boolean dfs(int i, boolean[] visited, boolean[] visiting, List<Integer>[] nb) {
            if (visiting[i]) return false;
            visiting[i] = true;
            
            if (nb[i] != null)
                for (Integer j : nb[i])
                    if (!visited[j] && !dfs(j, visited, visiting, nb)) return false;
            
            visiting[i] = true; visited[i] = true;
            return true;
        }
    }

Log in to reply
 

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