题解 | 任务调度

#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int maxn=100001;
struct node{
    int from;
    int to;
    node(int f,int t):from(f),to(t){}
};
vector<node>graph[maxn];
int main(){
    int n;
    cin>>n;
    int indegree[n];
    bool visit[n];
    for(int i=0;i<n;i++){
        indegree[i]=0;
        visit[i]=false;
    }
    for(int i=0;i<n;i++){
        string str;
        cin>>str;
        if(str[6]=='N'){
            continue;
        }
        int m=str[4]-'0';
        long long pos=10;
        while(str.size()>pos){
            int to=str[pos]-'0';
            indegree[to]++;
            pos+=6;
            graph[m].push_back(node(m,to));
        }
    }
    queue<int>qt;
    for(int i=0;i<n;i++){
        if(indegree[i]==0){
            qt.push(i);
            visit[i]=true;
        }
    }
    while(!qt.empty()){
        int n=qt.front();
        qt.pop();
        cout<<"Task"<<n<<" ";
        for(int i=0;i<graph[n].size();i++){
            int u=graph[n][i].to;
            indegree[u]--;
            if(indegree[u]==0&&visit[u]==false){
                qt.push(u);
                visit[u]=true;
            }
        }
    }
}