官方题解——烦人的依赖

B - 烦人的依赖

​软件的依赖关系可以看作一个有向图，而软件安装顺序就是求有向图的一个拓扑排序。注意题目中要求按照字典序排序，因此拓扑排序中要用优先队列。对于字符串的处理，可以先映射成整数，再做拓扑排序。
有的同学反映超时，可以试试看unordered_map，比map要少个log。

#include <bits/stdc++.h>
#include <cstring>
#define MAXN 30005
using namespace std;

int T, n, m, u, v, cnt=0, an;
string s, t;
string soft[MAXN];
int in[MAXN];
vector<int> edge[MAXN];
priority_queue<int> Q;
unordered_map<string, int> s2n;
int ans[MAXN];

void init(int n) {
    memset(in, 0, sizeof(in));
    while(!Q.empty())
        Q.pop();
    s2n.clear();
    for (int i=1; i<=n; ++i)
        edge[i].clear();
    an=0;
}

void solve() {
    scanf("%d%d", &n, &m);
    init(n);
    for (int i=1; i<=n; ++i)
        cin >> soft[i];
    sort(soft+1, soft+n+1, greater<string>());
    for (int i=1; i<=n; ++i)
        s2n[soft[i]]=i;
    for (int i=1; i<=m; ++i) {
        cin >> s >> t;
        ++in[s2n[t]];
        edge[s2n[s]].push_back(s2n[t]);
    }
    for (int i=1; i<=n; ++i) 
        if (!in[i]) Q.push(i);
    while(!Q.empty()) {
        u=Q.top(); Q.pop();
        ans[++an]=u;
        int len=edge[u].size();
        for (int i=0; i<len; ++i) {
            v=edge[u][i];
            if (!(--in[v])) Q.push(v);
        }
    }
    printf("Case #%d:\n", ++cnt);
    if (an!=n) {
        printf("Impossible\n");
        return;
    }
    for (int i=1; i<=an; ++i) {
        printf("%s\n", soft[ans[i]].c_str());
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}