题解 | #任务调度#

采用小根堆解题，代码可能有些冗余但思路很清晰：

1. 数据输入同时用数组保存每个点的入度（代码部分使用了vector解决）；
2. 设计小根堆排序规则：如果入读一样按照字典大小排序，入度不同则按照入读大小排序；
3. 扫描入读数组，将所有点入队；
4. 依次输出队头元素；

如有不足，请不吝赐教！

#include <iostream>
#include <queue>
#include <vector>
using namespace std;


struct node{
    int inNum;      // 入度
    int point;      // 点名称
};
bool operator<(node left,node right){   // 小根堆建立规则，入度最小优先，号码最小优先
    if(left.inNum == right.inNum) return left.point > right.point;
    else return left.inNum>right.inNum;
}


int main(){
    int num;string input;
    while(cin>>num){
        vector<int> in(num);                    //入度表
        for(int i=0;i<num;i++){
            cin>>input;
            // 计算入度
            if(input[6]=='N')continue;          // NULL
            long long unsigned int pos = 10;
            while(pos<input.size()){
                int to = input[pos]-'0';
                in[to]++;
                pos+=6;
            }
        }
        // 构建小根堆
        priority_queue<node> qu;
        for(int i=0;i<in.size();i++){
            node newNode;
            newNode.inNum = in[i];
            newNode.point = i;
            qu.push(newNode);
        }
        // 拓扑排序：
        while(!qu.empty()){
            cout<<"Task"<<qu.top().point<<" ";
            qu.pop();
        }

    }
}