题解 | #牛群的喂养顺序II#

• 题目考察的知识点 : 拓扑排序
• 题目解答方法的文字分析：

1. 和前一道题有点类似的思路，可以将牛之间的喂养顺序关系看作一张有向图，其中每头牛对应一个点，每条边表示一个喂养顺序关系。定义一个字典记录每个节点的入度，初始化为 0；
2. 遍历所有的边，将每个节点的入度增加 1；
3. 将所有入度为 0 的节点放入队列中；
4. 在队列中取出一个节点，将其加入答案数组中；
5. 遍历从节点出发的所有边，并将相应节点的入度减去 1；
6. 如果某个节点的入度变为 0，则将其加入队列中；
7. 重复步骤 4 - 6 直到队列为空。如果在处理完所有节点后，答案数组的长度不等于节点总数，则说明存在环，无法完成拓扑排序。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param numCows int整型
# @param feedOrders int整型二维数组
# @return int整型一维数组
#
import collections
class Solution:
    def findFeedOrderII(self, numCows: int, feedOrders: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCows)]
        indegree = [0] * numCows
        res = []

        for pre in feedOrders:
            graph[pre[1]].append(pre[0])
            indegree[pre[0]] += 1

        q = collections.deque([i for i in range(numCows) if indegree[i] == 0])

        while q:
            u = q.popleft()
            res.append(u)

            for v in graph[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)

        return res if len(res) == numCows else []