题目连接: Swapping Places
大致题意:
给定S种动物, L对朋友关系, N个动物, 如果两个相邻的动物是朋友关系, 则可以换序. 让你给n个动物排序, 希望尽可能按照字典序输出所有动物
解题思路:
拓扑排序, 由于两个不是朋友关系(或者为同种动物)的两个动物的前后相对位置是不会改变的(即 后面的动物不会排序到前面这个动物的前面). 所以我们可以以此约束建立拓扑图. 遍历每一个位置, 观察前面出现的动物有没有对当前动物产生约束的. 但这样的复杂度为O(n2).
优化: 其实我们每次只需要在当前位置遍历所有动物种类就可以了, 如果前面出现了多次某种动物, 没有必要都对当前动物建立约束(边), 因为同种动物自身也有约束, 例如ANT ANT, 如果前面的ANT不被排好序, 则其对后面ANT的约束是会一直存在的, 则后面ANT对其后其余位置的约束也会一直存在.
利用这个思路, 我们几番折腾可以完成排序!
AC代码:
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1E5 + 10;
bool g[205][205]; //记录两个物种间是否存在关系
vector<int> edge[N];
int du[N]; //表示入度
vector<string> name(1); //建立映射, 由编号得出名字 int->string
unordered_map<string, int> m; //建立映射, 由名字得出编号 string->int
int a[N], last[205]; //a表示当前位置的物种, last表示某物种最后出现的位置
set<pair<int, int>> st; //排序
int s, l, n;
void init() {cin >> s >> l >> n;/* 建立映射, int->string string->int */for (int i = 1; i <= s; ++i) {string str; cin >> str;name.push_back(str);}sort(name.begin(), name.end());int id = -1; //下标是从1开始的, vecotr初始化时存入了一个0for (auto& i : name) m[i] = ++id;/* 存关系 */while (l--) {string a, b; cin >> a >> b;int va1 = m[a], va2 = m[b];g[va1][va2] = g[va2][va1] = 1;}
}
void topo() {//初始化for (int i = 1; i <= n; ++i) {if (du[i] == 0) st.insert({ a[i] , i });}int cou = 0; //完成排序的数量while (!st.empty()) {cou++;auto op = st.begin()->first; //操作的物种auto index = st.begin()->second; //所处的位置st.erase(st.begin()); //移除这个元素cout << name[op];if (cou == n) cout << endl;else cout << ' ' << endl;int len = edge[index].size();for (auto i = 0; i < len; ++i) {auto to = edge[index][i];if (--du[to] == 0) st.insert({ a[to], to });}}
}
int main(void)
{cin.tie(0);ios::sync_with_stdio(0);init();/* 建图 */for (int i = 1; i <= n; ++i) {string str; cin >> str; a[i] = m[str];auto op = a[i]; //操作的物种编号for (int j = 1; j <= s; ++j) {if (g[op][j] || !last[j]) continue;edge[last[j]].push_back(i); //j这个物种对位置i有约束++du[i]; //约束++}last[op] = i;}/* 排序 */topo();return 0;
}
关于拓扑排序的理解: 按照边(点)对点的约束进行排序, 一个点的入度越大, 表明对其约束的边就越多, 则该点应在所有对其有约束的点都确定好顺序后才能排序.