题解

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

vector<string> topologicalSort(map<string, vector<string>>& graph, map<string, int>& inDegree) {
vector<string> result;
priority_queue<string, vector<string>, greater<string>> q; // 最小堆保证字典序

// 初始化队列
for (auto& entry : inDegree) {
    if (entry.second == 0) {
        q.push(entry.first);
    }
}

while (!q.empty()) {
    string u = q.top();
    q.pop();
    result.push_back(u);
    
    for (string v : graph[u]) {
        if (--inDegree[v] == 0) {
            q.push(v);
        }
    }
}

return result;

}

int main() {
int n;
while (cin >> n) {
map<string, vector<string>> graph;
map<string, int> inDegree;

    for (int i = 0; i < n; ++i) {
        string line;
        cin >> line;
        
        size_t left = line.find('(');
        string u = line.substr(0, left);
        string v_str = line.substr(left + 1, line.size() - left - 2);
        
        if (inDegree.find(u) == inDegree.end()) {
            inDegree[u] = 0;
        }
        
        if (v_str != "NULL") {
            size_t pos = 0;
            while ((pos = v_str.find(',')) != string::npos) {
                string v = v_str.substr(0, pos);
                graph[u].push_back(v);
                inDegree[v]++;
                v_str.erase(0, pos + 1);
            }
            graph[u].push_back(v_str);
            inDegree[v_str]++;
        }
    }
    
    vector<string> schedule = topologicalSort(graph, inDegree);
    
    for (size_t i = 0; i < schedule.size(); ++i) {
        if (i != 0) cout << " ";
        cout << schedule[i];
    }
    cout << endl;
}
return