C++ 解法, 执行用时: 3ms, 内存消耗: 556KB, 提交时间: 2022-02-08

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型vector<vector<>> 
     * @param n int整型 
     * @return int整型vector
     */
    vector<int> findOrder(vector<vector<int> >& prerequisites, int n) {
        int i,j,cur=0;
        bool correct=true;
        vector<bool> visited(n,false);
        vector<int> pre(n,-1),post(n,-1),res(n,-1);
        for(i=0;i<prerequisites.size();i++)
        {
            pre[prerequisites[i][0]]=prerequisites[i][1];
            post[prerequisites[i][1]]=prerequisites[i][0];
        }
        for(i=0;correct&&(i<n)&&(cur<n);i++)
        {
            if(pre[i]==-1)
            {
                for(j=i;correct&&(j!=-1)&&(cur<n);j=post[j])
                {
                    correct=(!visited[j]);
                    if(correct)
                    {
                        visited[j]=true;
                        res[cur]=j;
                        cur++;
                    }
                }
            }
        }
        correct=correct&&(cur>=n);
        if(!correct)
            res=vector<int>();
        return res;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 640KB, 提交时间: 2022-02-09

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型vector<vector<>> 
     * @param n int整型 
     * @return int整型vector
     */
    vector<int> findOrder(vector<vector<int> >& prerequisites, int n) {
        // write code here
        vector<int> res;
        vector<int> indeg(n, 0);
        vector<vector<int>> depend(n, vector<int>(0));
        for (vector<int>& pair : prerequisites) {
            int ori = pair[0], des = pair[1];
            depend[0].push_back(des);
            indeg[des]++;
        }
        queue<int> q;
        for (int i = 0; i < indeg.size(); i++) {
            if (indeg[i] == 0){
                q.push(i);
            }
        }
        while (! q.empty()) {
            int indep = q.front();
            q.pop();
            res.push_back(indep);
            for (int dep : depend[indep]) {
                indeg[dep]--;
                if (indeg[dep] == 0) {
                    q.push(dep);
                }
            }
        }
        if (res.size() == n) return res;
        return {};
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 516KB, 提交时间: 2021-12-07

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型vector<vector<>> 
     * @param n int整型 
     * @return int整型vector
     */
    vector<int> findOrder(vector<vector<int> >& prerequisites, int n) {
        // write code here
        vector<int> ret;
        vector<int> depend(n,-1);
        vector<int> next(n,-1);
        vector<int> weight(n,0);
        int i,j;
        for (i = 0; i< prerequisites.size(); i++){
            depend[prerequisites[i][0]] = prerequisites[i][1];
            next[prerequisites[i][1]] = prerequisites[i][0];
        }
        
        for (i = 0; i < n; i++){
            if (depend[i] == -1){
                weight[i]++;
                if (weight[i] > 1){
                    return vector<int>();
                }
                ret.push_back(i);
                j = next[i];
                while (j >= 0){
                    weight[j]++;
                    if (weight[j] > 1){
                        return vector<int>();
                    }
                    ret.push_back(j);
                    j = next[j];
                }
            }
        }
        return ret;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 528KB, 提交时间: 2022-07-07

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

C++ 解法, 执行用时: 4ms, 内存消耗: 548KB, 提交时间: 2022-05-08

class Solution {
  public:
    vector<int> findOrder(vector<vector<int> >& z, int n) {
        int i, j, cur = 0;
        bool correct = true;
        vector<bool> visited(n, false);
        vector<int> pre(n, -1), post(n, -1), res(n, -1);
        for (i = 0; i < z.size(); i++) {
            pre[z[i][0]] = z[i][1];
            post[z[i][1]] = z[i][0];
        }
        for (i = 0; correct && (i < n) && (cur < n); i++) {
            if (pre[i] == -1) {
                for (j = i; correct && (j != -1) && (cur < n); j = post[j]) {
                    correct = (!visited[j]);
                    if (correct) {
                        visited[j] = true;
                        res[cur] = j;
                        cur++;
                    }
                }
            }
        }
        correct = correct && (cur >= n);
        if (!correct)
            res = vector<int>();
        return res;
    }
};