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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numCows int整型 
     * @param feedOrders int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> findFeedOrderII(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);
        }
    }

    vector<int> result;
    // 进行拓扑排序
    while (!q.empty()) {
        int curCow = q.front();
        q.pop();
        result.push_back(curCow);

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

    if (result.size() == numCows) {
        return result;  // 存在一种可行的喂养顺序
    } else {
        return {};      // 无法喂养完所有牛
    }
    }
};