烦人的依赖

第一行包含一个正整数 T 表示数据组数。
每组数据的第一行包 n 和 m，表示有 n 个软件，m 个依赖关系。
接下来的一行包含 n 个软件名(软件名仅包含小写字母 a-z )
接下来的 m 行每行有两个软件名 s 和 t，表示 t 依赖 s ，即 s 要在 t 之前安装。
数据保证： $1 \le T \le 5$
$1 \le n \le 3 \times 10^{4}, 1 \le m \le 10^{5}$
$1 \le |s|,|t| \le 10$

共 T 组输出，每组输出先输出一行 Case #%d: ，%d 替换为当前输出的组数。
接下来是 n 行，按照安装的顺序输出。
如果无法进行安装，输出 Impossible (注意大小写)。

C++ 解法, 执行用时: 754ms, 内存消耗: 6520K, 提交时间: 2021-12-01 21:27:42

#include<bits/stdc++.h>
using namespace std;

int n,m,t;
int main() {
	cin>>t;
	for(int i=1; i<=t; i++) {
		cin>>n>>m;
		map<string,int> ma;
		vector<int>ve[30010],ans;
		int ind[30010]= {};
		string s,a,b,d[30010];
		for(int i=0; i<n; i++) {
			cin>>s;
			d[i]=s;
		}
		sort(d,d+n);
		for(int i=0; i<n; i++)ma[d[i]]=i;
		for(int i=0; i<m; i++) {
			cin>>a>>b;
			int x=ma[a],y=ma[b];
			ve[x].push_back(y);
			ind[y]++;
		}
		priority_queue<int>qu;
		for(int i=0; i<n; i++)
			if(!ind[i])qu.push(-i);
		while(qu.size()) {
			int k=-qu.top();
			ans.push_back(k);
			qu.pop();
			for(int i=0; i<ve[k].size(); i++) {
				ind[ve[k][i]]--;
				if(!ind[ve[k][i]])qu.push(-ve[k][i]);
			}
		}
		cout<<"Case #"<<i<<":"<<endl;
		if(ans.size()<n)puts("Impossible");
		else {
			for(int i=0; i<ans.size(); i++)
				cout<<d[ans[i]]<<endl;
		}
	}

	return 0;
}

详情