西邮第五届ACM-ICPC B 烦人的依赖 题解

题目大意

给你n个字符串，给你其中m个的优先关系，需要先输出字典序小的字符串，问你能否成立，能的话输出序列。

解题思路

由于需要按照字典序的顺序来输出，所以需要使用优先队列（小顶堆）。

告诉了我们每对的优先关系，可以构造出一个图，用拓扑排序来判断是否有环来判断是否成立。

字符串与位置的对应关系需要使用unorder_map，map会超时。。

用一个vector来记录路径。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 5e4 + 5;
unordered_map<string, int>M;
priority_queue<string,vector<string>,greater<string>> q;
string ss[N];
vector<int>Map[N];
vector<string> p;
int in[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t,c = 1;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		string s1,s2;
		memset(in, 0, sizeof(in));
		for (int i = 1; i <= n; i++) {
			Map[i].clear();
			cin >> ss[i];
		}
		sort(ss + 1, ss + 1 + n);
		for (int i = 1; i <= n; i++) {
			M[ss[i]] = i;
		}
		for (int i = 1; i <= m; i++) {
			cin >> s1 >> s2;
			int n1 = M[s1], n2 = M[s2];
			Map[n1].push_back(n2);
			in[n2]++;
		}
		for (int i = 1; i <= n; i++) {
			if (!in[M[ss[i]]])	q.push(ss[i]);
		}
		while (!q.empty()) {
			int f = M[q.top()];
			p.push_back(ss[f]);
			q.pop();
			for (auto x = Map[f].begin(); x != Map[f].end(); x++) {
				in[*x]--;
				if(!in[*x])	q.push(ss[*x]);
			}
		}
		cout << "Case #" << c++ << ":" << endl;
		if (p.size() == n) {
			for (auto x : p)cout << x << endl;
		}
		else  cout << "Impossible" << endl;
		p.clear();
	}
}