拓扑排序：编译依赖问题

一个完整的软件项目往往会包含很多由代码和文档组成的源文件。编译器在编译整个项目的时候，可能需要按照依赖关系来依次编译每个源文件。比如，A.cpp 依赖 B.cpp，那么在编译的时候，编译器需要先编译 B.cpp，才能再编译 A.cpp。 假设现有 0，1，2，3 四个文件，0号文件依赖1号文件，1号文件依赖2号文件，3号文件依赖1号文件，则源文件的编译顺序为 2,1,0,3 或 2,1,3,0。现给出文件依赖关系，如 1,2,-1,1，表示0号文件依赖1号文件，1号文件依赖2号文件，2号文件没有依赖，3号文件依赖1号文件。请补充完整程序，返回正确的编译顺序。注意如有同时可以编译多个文件的情况，按数字升序返回一种情况即可，比如前述案例输出为：2,1,0,3.

示例1

输入
“1,2,-1,1”
输出
“2,1,0,3”

备注:

-1 表示当前文件没有依赖，输出结果用英文逗号分隔。暂不考虑一个文件依赖多个文件的情况。

本题的主要思想可以参考LC 207. 课程表

ACM模式下的C++代码实现：

#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

bool compare(int a, int b)
{
    return a > b;   //降序排列，如果改为return a<b，则为升序
}

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& adj) {
        vector<int> flags(numCourses, 0);
        vector<int> res(numCourses);
        res.clear();
        for (int i = numCourses - 1; i >= 0; i--) {
            //题目要求按数字升序排列，这里从数字大的节点开始dfs，因此在结果数组中的位置会更靠后（使用的是insert函数）
            if (!dfs(adj, flags, i, res)) return vector<int>();
        }
        return res;
    }
private:
    bool dfs(vector<vector<int>>& adj, vector<int>& flags, int i, vector<int>& res) {
        if (flags[i] == 1) return false;    //本次搜索来过此节点，说明存在环
        if (flags[i] == -1) return true;    //说明此点已经被其他点启动的dfs访问过，返回true
        flags[i] = 1;
        for (int j : adj[i]) {
            if (!dfs(adj, flags, j, res)) return false;
        }
        flags[i] = -1;
        res.emplace(res.begin(), i);        //将此点加入要返回的结果数组中
        return true;
    }
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 编译顺序
     * @param input string字符串
     * @return string字符串
     */
    string compileSeq(string input) {
        // write code here
        int i = 0;      //记录文件个数
        vector<int> nums;
        while (!input.empty()) {
            if (input.find(',') == string::npos) {
                nums.push_back(stoi(input));
                input.clear();
                i++;
                break;
            }
            string tmp = input.substr(0, input.find(','));
            nums.push_back(stoi(tmp));
            input.erase(0, input.find(',') + 1);
            i++;
        }
        vector<vector<int>> adj(i, vector<int>());      //前驱节点链表生成
        for (int j = 0; j < i; j++) {
            if (nums[j] == -1) continue;        //没有文件依赖的情况，跳过
            adj[nums[j]].push_back(j);
        }
        for (int j = 0; j < adj.size(); j++) {
            if (adj[j].size() >= 2) {
                sort(adj[j].begin(), adj[j].end(), compare);    //对每个结点的前驱结点进行升序排列，数字大的先进行dfs，在结果数组中的位置更靠后（使用insert函数），这样输出的时候才能按数字升序返回
            }
        }
        vector<int> res = findOrder(i, adj);    //使用dfs进行搜索
        string s;
        //输出
        for (int j = 0; j < i; j++) {
            s += to_string(res[j]);
            if (j < i - 1) {
                s.push_back(',');
            }
        }
        return s;
    }
};


int main() {
    string str;
    getline(cin, str);          //从命令行获取字符串
    Solution st;
    cout << st.compileSeq(str);
    return 0;
}

运行结果：