LeetCode 207. Course Schedule

Dfs.java

public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Set<Integer>> adj = new ArrayList<>(numCourses);
        for(int i = 0; i < numCourses; ++i) adj.add(new HashSet<Integer>());
        
        for(int[] edge: prerequisites ) adj.get(edge[1]).add(edge[0]);
        
        boolean[] done = new boolean[numCourses];
        boolean[] visited = new boolean[numCourses];
        for(int i = 0; i < numCourses; ++i) {
            if(hasCycle(adj, visited, done, i)) return false;
        }
        return true;
    }
    
    public boolean hasCycle(List<Set<Integer>> adj, boolean[] visited, boolean[] done, int start) {
        if (visited[start]) return true;
        if (done[start]) return false;
      
        visited[start] = true;
        for(Integer i : adj.get(start)) 
            if (hasCycle(adj, visited, done, i)) return true;
        visited[start] = false;
        
        done[start] = true; // return false means no cycle -> can be done, memo result for all nodes on dfs path
        return false;
    }

TopologicalSorting.java

public boolean canFinish(int numCourses, int[][] prerequisites) {
        // build the adj list
        // build startNode List for in degree is zero
        List<Set<Integer>> adj = new ArrayList<>();
        int[] inDegrees = new int[numCourses];
        for(int i = 0; i < numCourses; ++i) adj.add(new HashSet<Integer>());
        for(int[] edge : prerequisites) {
            if (!adj.get(edge[0]).contains(edge[1])) {
                adj.get(edge[0]).add(edge[1]);
                inDegrees[edge[1]]++;
            }
        }
        
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < numCourses; ++i) if(inDegrees[i] == 0) q.offer(i);
        
        // topology and update numCourse -= startNodeList.size()
        while(q.size() != 0) {
            Integer i = q.poll();
            for (int neighbor : adj.get(i)) {
                --inDegrees[neighbor];
                if(inDegrees[neighbor] == 0) q.offer(neighbor);
            }
            --numCourses;
        }
        
        return numCourses == 0;
    }

DFS runs 13ms, Topological sorting runs 17ms

Both time complexity is O(V + E), but dfs don't need traverse whole graph when there's a cycle