leetcode 207. Course Schedule | 207. 课程表（Java）-蒲公英云

leetcode 207. Course Schedule | 207. 课程表（Java）

题目

https://leetcode.com/problems/course-schedule/
在这里插入图片描述

题解

这的道题思路，来源于数据结构中的 拓扑排序 问题，主要思路是，通过逐步遍历删除入度为 0 的节点，判断该图是否一个有向无环图（DAG）。即，判断该图是否满足两个条件：

必须能够连通所有节点（分析本题场景发现，可以不经过所有节点）
不能有环

详细解题思路见下图：
在这里插入图片描述

import java.util.ArrayList;
class Node { 
    int inDegree;
    ArrayList<Integer> children;
    boolean alive; // whether deleted
    public Node() { 
        alive = true;
        children = new ArrayList<>();
    }
}
class Solution { 
    public boolean canFinish(int numCourses, int[][] prerequisites) { 
        // init courses
        Node[] nodes = new Node[numCourses];
        for (int i = 0; i < numCourses; i++) { 
            nodes[i] = new Node();
        }
        // init prerequisites
        for (int i = 0; i < prerequisites.length; i++) { 
            nodes[prerequisites[i][0]].children.add(prerequisites[i][1]);
            nodes[prerequisites[i][1]].inDegree++;
        }
        // check DAG
        int remain = numCourses; // remaining nodes
        boolean valid = true; // last loop really works
        while (valid && remain > 0) { 
            valid = false;
            for (int i = 0; i < numCourses; i++) { 
                if (nodes[i].inDegree == 0 && nodes[i].alive) { 
                    for (int n : nodes[i].children) {  // update
                        nodes[n].inDegree--;
                    }
                    valid = true;
                    nodes[i].alive = false;
                    remain--;
                }
            }
        }
        return remain == 0;
    }
}