题解 | #牛牛吃水果的顺序#

#include <set>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numFruits int整型 
     * @param prerequisites int整型vector<vector<>> 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > findFruitOrder(int numFruits, vector<vector<int> >& prerequisites) {
        // write code here
        vector<int> pos;
        vector<vector<int> > output;
        for(int i = 0; i<numFruits;i++){
            pos.emplace_back(i);
        }
        vector<bool> verify(numFruits,false);
        next:do{
            verify.clear();
            verify = vector<bool>(numFruits,false);
            for (int i = 0 ; i < numFruits ; i++) {
                bool flag = true;
                for(int j = 0 ; j < prerequisites.size() ; j++){
                    if(prerequisites[j][0] == pos[i] && !verify[prerequisites[j][1]]){
                        flag = false;
                        break;
                    }
                }
                if(!flag){
                    if(next_permutation(pos.begin(),pos.end())){
                        goto next;
                    }else return output;
                }
                verify[i] = true;
            }
            output.emplace_back(pos);
        }while(next_permutation(pos.begin(),pos.end()));

        return output;
    }
};

垃圾办法，全排列之后挨个数字放到prerequisites里面比较，如果prerequisites[i][0]有这个数那就看prerequisites[i][1]这个数之前吃没吃过，如果吃过了就继续从排列里面从左往右遍历，没吃过直接flag给false转到下一个排列。

#include <vector> #include <algorithm> using namespace std; class Solution { public: vector<vector<int>> findFruitOrder(int numFruits, vector<vector<int>>& prerequisites) { // 构建图和入度数组 vector<vector<int>> graph(numFruits); vector<int> inDegree(numFruits, 0); for (const auto& p : prerequisites) { graph[p[1]].push_back(p[0]); inDegree[p[0]]++; } // 找到所有入度为0的节点 vector<int> sources; for (int i = 0; i < numFruits; i++) { if (inDegree[i] == 0) sources.push_back(i); } vector<vector<int>> orders; vector<int> path; dfs(graph, inDegree, sources, path, orders); return orders; } private: void dfs(vector<vector<int>>& graph, vector<int>& inDegree, vector<int>& sources, vector<int>& path, vector<vector<int>>& orders) { if (sources.empty()) { if (path.size() == graph.size()) orders.push_back(path); return; } for (int i = 0; i < sources.size(); i++) { int source = sources[i]; sources.erase(sources.begin() + i); path.push_back(source); vector<int> nextSources = sources; for (int child : graph[source]) { inDegree[child]--; if (inDegree[child] == 0) nextSources.push_back(child); } dfs(graph, inDegree, nextSources, path, orders); // 回溯 path.pop_back(); sources.insert(sources.begin() + i, source); for (int child : graph[source]) inDegree[child]++; } } };