Gym 102501G Swapping Places (拓扑排序)
程序员文章站
2024-03-19 12:17:46
...
题意:给定S种动物, L对朋友关系, N个动物, 如果两个相邻的动物是朋友关系, 则可以换序. 让你给n个动物排序, 按照字典序最小输出所有动物。
题解:拓扑排序
相同动物的位置关系一定固定,考虑不是朋友关系的动物,则它们的两两相对位置一定不变,这样就构成了约束,用
l
a
s
t
[
]
last[]
last[]存储上一个不是朋友关系的动物位置,然后建图,跑拓扑排序即可。
由于要按照字典序最小输出,用优先队列优先取出字典序最小的即可。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
#define pii pair<int, int>
using namespace std;
int s, l, n, g[222][222], last[222], id[100005];
string str, x, y;
vector<string> ss;
map<string, int> m;
//bfs
vector<int> topo, G[100005];
int in_deg[100005];
bool toposort() {
topo.clear();
priority_queue<pii, vector<pii>, greater<pii> > q;
for (int i = 1; i <= n; i++)
if (in_deg[i] == 0) q.push({ id[i], i });
while (!q.empty()) {
pii temp = q.top();
q.pop();
topo.push_back(temp.first);
for (auto v : G[temp.second]) {
if (--in_deg[v] == 0) q.push({ id[v], v });
}
}
if (topo.size() == n) return true;
else return false;
}
int main() {
scanf("%d%d%d", &s, &l, &n);
for (int i = 1; i <= s; i++) {
cin >> str;
ss.push_back(str);
}
sort(ss.begin(), ss.end());
for (int i = 0; i < s; i++) {
m[ss[i]] = i + 1;
}
for (int i = 1; i <= l; i++) {
cin >> x >> y;
g[m[x]][m[y]] = g[m[y]][m[x]] = 1;
}
for (int i = 1; i <= n; i++) {
cin >> str;
id[i] = m[str];
for (int j = 1; j <= s; j++) {
if (g[id[i]][j] || !last[j]) continue;
G[last[j]].push_back(i);
in_deg[i]++;
}
last[id[i]] = i;
}
toposort();
for (auto i : topo) cout << ss[i - 1] << " ";
return 0;
}
上一篇: PSR4自动加载 博客分类: PHP
下一篇: RSA加密工具