企业官网建设流程全解析

题目

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

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

• 例如，先修课程对[0, 1]表示：想要学习课程0，你需要先完成课程1。

请你判断是否可能完成所有课程的学习？如果可以，返回true；否则，返回false。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]输出：true解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]输出：false解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i]中的所有课程对互不相同

题解

class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { int[] inDgree = new int[numCourses];//存每门课的入度数 List<List<Integer>> adjList = new ArrayList<>();//存前置->后置 for(int i = 0;i < numCourses;i++){ adjList.add(new ArrayList<>()); } for(int[] prerequisite : prerequisites){ int course = prerequisite[0]; int preCourse = prerequisite[1]; inDgree[course]++; //adjList.get(x).add(y)：往 x 对应的子列表追加 y adjList.get(preCourse).add(course); } Queue<Integer> queue = new LinkedList<>(); for(int i = 0;i < numCourses;i++){ if(inDgree[i] == 0){ queue.offer(i); } } int count = 0; while(!queue.isEmpty()){ int selectedCourse = queue.poll(); count++; List<Integer> nextCourses = adjList.get(selectedCourse); for(int nextCourse : nextCourses){ inDgree[nextCourse]--; if(inDgree[nextCourse] == 0){ queue.offer(nextCourse); } } } return count == numCourses;//环内节点入度永远不为 0，导致count偏小 } }

思路

思路：不断挑选当前没有前置条件（入度 = 0）的节点。

1. 构建图（邻接表）
2. 记录每一个节点入度
3. 将入度等于 0 节点送入队列
4. 循环取出节点，消除该节点向外发出的边，邻居入度 -1。邻居入度归零加入队列。
5. 统计一共取出多少节点。

• 取出节点总数 = 全部节点：无环 ，课程可以全部学完
• 取出数量 < 总节点：存在环路，环内节点入度永远不为 0，无法被选出来。返回 false