拓扑排序 | #任务调度#

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;

int main() {
    int n;
    map<string, int> degree;//入度
    map<string, vector<string>> grid;//邻接矩阵
    set<string> nodes;
    while (cin >> n) { // 注意 while 处理多个 case
        string task;
        for (int i = 0; i < n; i++) {
            cin>>task;
            int index=task.find('(');
            string s1=task.substr(0,index);
            nodes.insert(s1);
            string tmp="";
            for(int j=index+1;j<task.size();j++){
                if((task[j]==','||task[j]==')')&&tmp.compare("NULL")!=0){
                    // arr.push_back(tmp);
                    grid[s1].push_back(tmp);
                    degree[tmp]++;//入度增加
                    nodes.insert(tmp);
                    tmp="";
                }else
                    tmp+=task[j];
            } 
        }
        queue<string> q;
        for(string s:nodes){
            if(degree[s]==0)
                q.push(s);      
        }
        vector<string> ans;
        while(!q.empty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                string x=q.front();
                q.pop();
                ans.push_back(x);
                for(string neb:grid[x]){
                    degree[neb]--;
                    if(degree[neb]==0)
                        q.push(neb);
                }
            }
        }
        for_each(ans.begin(),ans.end(),[](string x){cout<<x<<" ";});
    }
}
// 64 位输出请用 printf("%lld")