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

考察知识点： 拓扑排序、队列

题目分析：

 做一件事之前必须先完成一些事，这样的做事顺序就是拓扑序列。可以使用队列判断一个序列能否是拓扑序。

 首先如果做一件事之前不需要做其他事，那么我们就可以选择完成这一件事。当这一件事完成之后，可能就会有依赖这件事的事情可以做了。对该题而言，首先记录每个节点被哪些结点依赖，然后记录每一个结点的入度。

 记录完所有的事件后，遍历所有事件的入度，如果为0那么我们就将其加入到队列中。完成后对队列中的元素进行访问，每次访问完毕后将结点加入到vector中并释放该节点，那么依赖该结点的事件就有可能入度为0了。将入度为0的序列加入到队列中等待被重复上述处理即可。

 当队列中处理完毕后，如果访问到的牛的数量小于给出的牛的数量，说明在处理过程中产生了环，使得该环中的所有牛的入度都不为0，返回空vector即可；否则返回包含答案的vector即可。

所用编程语言： C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numCows int整型 
     * @param feedOrders int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> findFeedOrderII(int numCows, vector<vector<int> >& feedOrders) {
        // write code here
        vector<vector<int>> next(numCows);
        vector<int> indegree(numCows);
        queue<int> zeroq;
        vector<int> res;

        for (auto &feedOrder: feedOrders) {
            int ai = feedOrder[0];
            int bi = feedOrder[1];
            next[bi].push_back(ai);
            indegree[ai]++;
        }

        for (int i = 0 ; i < numCows; i++) {
            if (indegree[i] == 0) 
                zeroq.push(i);
        }

        while (!zeroq.empty()) {
            int cow = zeroq.front();
            zeroq.pop();
            numCows--;
            res.push_back(cow);
            for (auto &nextCow: next[cow]) {
                if (--indegree[nextCow] == 0) zeroq.push(nextCow);
            }
        }

        if (!numCows) return res;
        else return {};
    }
};