题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses – 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

题目分析

记录每个点的入度，及后续的点（邻接表）
BFS，从入度为 0 的点开始
每访问一个点，将后续点的入度减1，然后将其中入度为0的入队
最后检查一遍是否存在入度 > 0 的点

Java

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] pre = new int[numCourses];
    List<List<Integer>> next = new ArrayList<>();
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        next.add(new ArrayList<>());
    }
    for (int[] pair : prerequisites) {
        pre[pair[0]]++;
        next.get(pair[1]).add(pair[0]);
    }
    for (int i = 0; i < numCourses; i++) {
        if (pre[i] == 0) {
            queue.offer(i);
        }
    }
    while (!queue.isEmpty()) {
        Integer x = queue.poll();
        List<Integer> list = next.get(x);
        for (Integer i : list) {
            pre[i]--;
            if (pre[i] == 0) {
                queue.offer(i);
            }
        }
    }
    for (int i = 0; i < numCourses; i++) {
        if (pre[i] > 0) {
            return false;
        }
    }
    return true;
}

Kotlin

fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
    val pre = IntArray(numCourses)
    val next = Array(numCourses) { ArrayList<Int>() }
    val queue = LinkedList<Int>()
    for (array in prerequisites) {
        pre[array[0]]++
        next[array[1]].add(array[0])
    }
    for (i in 0 until numCourses) {
        if (pre[i] == 0) {
            queue.offer(i)
        }
    }

    while (!queue.isEmpty()) {
        val num = queue.poll()

        for (i in next[num]) {
            pre[i]--
            if (pre[i] == 0) {
                queue.offer(i)
            }
        }
    }

    for (i in 0 until numCourses) {
        if (pre[i] > 0) {
            return false
        }
    }
    return true
}