欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 210. 课程表II

程序员文章站 2022-04-04 10:06:18
...

题目描述

Leetcode 210. 课程表II
Leetcode 210. 课程表II

代码实现

(C#)

public class Solution {
    public int[] FindOrder(int numCourses, int[][] prerequisites) 
    {
         if (numCourses == 0) return new int[0];
        int[] inDegrees = new int[numCourses];
        // 建立入度表
        foreach(int[] p in prerequisites) { // 对于有先修课的课程,计算有几门先修课
            inDegrees[p[0]]++;
        }
        // 入度为0的节点队列
        Queue<int> queue = new Queue<int>();
        for (int i = 0; i < inDegrees.Length; i++) {
            if (inDegrees[i] == 0) queue.Enqueue(i);
        }
        int count = 0;  // 记录可以学完的课程数量
        int[] res = new int[numCourses];  // 可以学完的课程
        // 根据提供的先修课列表,删除入度为 0 的节点
        while (queue.Count != 0){
            int curr = queue.Dequeue();
            res[count++] = curr;   // 将可以学完的课程加入结果当中
            foreach (int[] p in prerequisites) {
                if (p[1] == curr){
                    inDegrees[p[0]]--;
                    if (inDegrees[p[0]] == 0) queue.Enqueue(p[0]);
                }
            }
        }
        if (count == numCourses) return res;
        return new int[0];
    }
}

Leetcode 210. 课程表II

Leetcode 210. 课程表II