题解 | #任务调度#

#include <iostream>
#include <cstring>
#include <queue>

const int N = 100010;

using namespace std;

int n;
string str;
vector<int> h[N];                                 // 邻接表
int degree[N];                                    // 记录顶点入度
priority_queue<int, vector<int>, greater<int>> q; // greater将最小的元素放在队首——>为了输出字典序最小的方案

int main()
{
    while (cin >> n)
    {
        // 建图的同时记录入度
        memset(h, 0, sizeof(h));
        memset(degree, 0, sizeof(degree));
        for (int i = 0; i < n; i++)
        {
            cin >> str;
            if (str.substr(6, 4) == "NULL")
                continue;
            for (int j = 10; j < str.size(); j += 6)
                h[i].push_back(str[j] - '0'), degree[str[j] - '0']++;
        }
        // 初始化优先队列
        for (int i = 0; i < n; i++)
            if (degree[i] == 0)
                q.push(i);
        // 拓扑排序
        while (q.size() != 0)
        {
            // 出队
            int ver = q.top();
            q.pop();
            // 打印
            cout << "Task" << ver << " ";
            // 更新入度并入队
            for (int i = 0; i < h[ver].size(); i++)
                if (--degree[h[ver][i]] == 0)
                    q.push(h[ver][i]);
        }
        cout << endl;
    }
}