Kitchen Plates (拓扑排序)

原题链接

题意

给五个关系像"A<B"这种，问根据这些关系，问这些关系是否有矛盾，有矛盾的话就输出“impossible”，没有的话尽量从小到大输出这些东西。

思路

直接拓扑排序即可，输出拓扑序列。

代码

#include<bits/stdc++.h>
using namespace std;const int N = 10005;vector<int> g[N], ans;
int d[N];
int n = 5;
bool topsort()
{
    queue<int> q;for (int i = 1; i <= n; i ++ ){
    if (d[i] == 0){
    q.push(i);ans.push_back(i);}}while (!q.empty()){
    int t = q.front();q.pop();for (int i = 0; i < g[t].size(); i ++ ) {
    int j = g[t][i];d[j] --;if (d[j] == 0){
    q.push(j);ans.push_back(j);}}}return ans.size() == n;
}
int main()
{
    map<char, int> f;f['A'] = 1;f['B'] = 2;f['C'] = 3;f['D'] = 4;f['E'] = 5;map<int, char> ff;ff[1] = 'A';ff[2] = 'B';ff[3] = 'C';ff[4] = 'D';ff[5] = 'E';string s;for (int i = 1; i <= 5; i ++ ){
    cin >> s;if (s[1] == '<'){
    g[f[s[0]]].push_back(f[s[2]]);d[f[s[2]]] ++;}else{
    g[f[s[2]]].push_back(f[s[0]]);d[f[s[0]]] ++;}}bool ss = topsort();if (ss) for (int i : ans) cout << ff[i];else cout << "impossible";cout << endl;return 0;
}

总结

模板题。

还有就是发现了CF的彩蛋，Accept~变成了HAPPY NEW YEAR.