34ms Java BFS toposort with Kahn's algorithm


  • 0
    Y

    Note: I used Kahn's algorithm to dynamically update the indegrees of vertices, which can be visualized as removing incoming edges.

    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            // BFS topological sorting with Kahn's algorithm
            // if cycle is detected, return false
            int[] indegree = new int[numCourses];
            for (int[] p : prerequisites) {
                indegree[p[0]]++;
            }
            // queue for nodes with indegree == 0
            LinkedList<Integer> queue = new LinkedList<Integer>();
            for (int i = 0; i < indegree.length; i++) {
                if (indegree[i] == 0) {
                    queue.offer(i);
                }
            }
            int canFinish = 0;
            while (queue.size() != 0) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Integer curr = queue.poll();
                    canFinish++;
                    for (int[] p : prerequisites) {
                        if (p[1] == curr) {
                            indegree[p[0]]--;
                            if (indegree[p[0]] == 0) {
                                queue.offer(p[0]);
                            }
                        }
                    }
                }
            }
            return canFinish == numCourses;
        }
    }

Log in to reply
 

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