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

// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * 
//      * @param numCows int整型 
//      * @param feedOrders int整型vector<vector<>> 
//      * @return bool布尔型
//      */
//     bool canFeedAllCows(int numCows, vector<vector<int> >& feedOrders) {
//         // write code here
//         vector<vector<int>> next(numCows);
//         vector<int> indegree(numCows);
//         queue<int> zeroq;
//         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--;
//             for (auto &nextCow: next[cow]) {
//                 if (--indegree[nextCow] == 0) zeroq.push(nextCow);
//             }
//         }

//         if (numCows) return false;
//         else return true;
//     }
// };


#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numCows int整型 
     * @param feedOrders int整型vector<vector<>> 
     * @return bool布尔型
     */
    bool canFeedAllCows(int numCows, vector<vector<int> >& feedOrders) {
        // write code here
        // 以ai为“先修课”的牛的数量
        vector<int> v(numCows,0);
        // 以ai为“先修课”的牛有哪一些
        vector<vector<int>> v_v(numCows);

        for(const auto info:feedOrders)
        {
            // info[1]先喂
            v_v[info[1]].emplace_back(info[0]);
            // info[0]得为0，才表示它能开始喂
            ++v[info[0]];
        }

        queue<int> q_v;
        for(int i=0; i<numCows; ++i)
        {
            // 牛 i 没有限制，不需要喂养其它牛后才来喂养v[i]
            if(v[i]==0)
                q_v.emplace(i);
        }

        while(!q_v.empty())
        {
            // 修改之后
            int i = q_v.front();
            q_v.pop();
            --numCows;

            for(auto temp: v_v[i])
            {
                --v[temp];
                // 如果t[j]的“先修课”为 0，则加入队列
                if(v[temp]==0)
                    q_v.emplace(temp);
            }
        }

        return numCows==0 ? true : false;
    }
};