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

这是一个典型的拓扑排序问题。我们可以将牛群之间的喂养顺序关系看作是一个有向图，每个牛表示一个顶点，有向边表示喂养的顺序关系。

要判断是否可以按照喂养顺序关系完成所有牛的喂养，我们可以使用拓扑排序算法来解决。拓扑排序通过构建有向图的拓扑序列，检测是否存在环来判断是否有可能完成拓扑排序。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numCows int整型
     * @param feedOrders int整型vector<vector<>>
     * @return bool布尔型
     */
    bool canFeedAllCows(int numCows, vector<vector<int> >& feedOrders) {
        vector<vector<int>> adjList(numCows);  // 有向图的邻接表表示
        vector<int> indegree(numCows, 0);  // 保存每个顶点的入度

        // 构建有向图
        for (auto& order : feedOrders) {
            int cowToFeed = order[0];
            int cowToPreFeed = order[1];
            adjList[cowToPreFeed].push_back(cowToFeed);
            indegree[cowToFeed]++;
        }

        queue<int> q;
        // 将入度为 0 的顶点入队列
        for (int i = 0; i < numCows; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        int count = 0;  // 记录已经处理的顶点数量

        while (!q.empty()) {
            int curCow = q.front();
            q.pop();
            count++;

            // 处理当前顶点的邻接顶点
            for (int neighbor : adjList[curCow]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return count == numCows;
        // write code here
    }
};