207. 课程表

package treeAndRecursion.code207;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
 * 经典的拓扑排序的问题
 * 知识点：
 * 1：无向图的度数，就是无向图中，和这个点相连的点的数量
 * 2：有向图的度数。入度：进入这个点的数量。出度：从这个点出去的数量。
 *
 * 引申到题目，什么课程（点）可以直接修呢？就是入度为0的点，可以直接修。
 * 所以要做拓扑排序，要先统计途中点的入度
 *
 */
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //1：初始化
        //1.1 初始化出边数组,就是初始化图，建立边的关系
        to = new ArrayList<List<Integer>>();
        for(int i = 0 ; i < numCourses ; i ++){
            to.add(i,new ArrayList<>());
        }
        // 1.2 初始化统计图的入度的数组
        inDeg = new int[numCourses];
        // 1.3 记录BFS中，修过了那些课程
        List<Integer> lesson = new ArrayList<>();
        for(int[] pre : prerequisites){
            //根据题意，第一个是ai第二个是bi
            int ai = pre[0];
            int bi = pre[1];
            //如果想修ai要先修bi的话，要从bi -> ai 建边
            to.get(bi).add(ai);
            //当加了一条边，是指向ai的，则入度统计里，ai + 1
            inDeg[ai] ++;
        }
        //2: 要执行BFS，广度优先遍历，要先入队
        Queue<Integer> queue = new LinkedList<>();
        //2.1 遍历所有入度统计数组，当时入度为0的，说明是可以直接修的
        // 拓扑排序的第一步：从0入度出发作为起点。
        for (int i = 0; i < numCourses; i ++){
            //如果入度为0，则放入队列
            if(inDeg[i] == 0){
                //入队就表示可以修了
                queue.add(i);
            }
        }
        //3: 执行BFS
        while (!queue.isEmpty()){
            // 3.1 x 出队，代表x 可以修了。然后记录x修过了
            int x = queue.poll();
            lesson.add(x);
            // 拓扑排序的第二步：扩展一个点，周围点的入度-1
            for(int y : to.get(x)){
                inDeg[y]--;
                // 拓扑排序的第三步：入度减为0，说明可以入队了
                //说明这门课程的全部先修课都被修完了
                if(inDeg[y] == 0){
                    queue.add(y);
                }
            }
        }
        //4:返回值。如果修过的课程数 = 全部课程数，则返回true，否则false
        return lesson.size() == numCourses;
    }
    //使用出边数组构建图
    private List<List<Integer>> to;
    //统计图中点的入度的数组
    private int[] inDeg;
}