My BFS solution using java


  • 0
    F

    public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] degree = new int[numCourses];
    List[] edges = new ArrayList[numCourses];

        for (int i = 0; i < numCourses; i++) {
            edges[i] = new ArrayList<Integer> ();
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int start = prerequisites[i][1];
            int end = prerequisites[i][0];
            degree[end]++;
            edges[start].add(end);
        }
        
        Queue<Integer> q = new LinkedList<> ();
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) {
                q.offer(i);
            }
        }
        int count = 0;
        while (!q.isEmpty()) {
            int start = q.poll();
            count++;
            List<Integer> endList = edges[start];
            for (int i : endList) {
                degree[i]--;
                if (degree[i] == 0) {
                    q.offer(i);
                }
            }
        }
        return count == numCourses;
        
    }
    

    }


Log in to reply
 

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