Java BFS solution with easily understood name


  • 0
    A
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses == 0 || prerequisites.length == 0) {
            return true;
        }
        int preCount[] = new int[numCourses];
        HashMap<Integer, List<Integer>> dependentMap = new HashMap<Integer, List<Integer>>();
        for (int[] item : prerequisites) {
            preCount[item[0]]++;
            if (dependentMap.containsKey(item[1])) {
                dependentMap.get(item[1]).add(item[0]);
            } else {
                List<Integer> list = new ArrayList<Integer>();
                list.add(item[0]);
                dependentMap.put(item[1], list);
            }
        }
        int freeCount = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; i++) {
            if (preCount[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int free = queue.poll();
            freeCount++;
            if (dependentMap.get(free) != null) {
                for (int dependent : dependentMap.get(free)) {
                    preCount[dependent]--;
                    if (preCount[dependent] == 0) {
                        queue.offer(dependent);
                    }
                }
            }
        }
        return freeCount == numCourses;
    }

Log in to reply
 

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