题目描述

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 A,B,C,D 表示A

输入格式

第一行有两个正整数 n,m,n 表示需要排序的元素数量，2≤n≤26，第 1 到 n 个元素将用大写的 A,B,C,D… 表示。m 表示将给出的形如A

接下来有 m 行，每行有 3 个字符，分别为一个大写字母，一个 < 符号，一个大写字母，表示两个元素之间的关系。

输出格式

若根据前 xx 个关系即可确定这 nn 个元素的顺序 yyy..y（如 ABC），输出

Sorted sequence determined after xxx relations: yyy...y.

若根据前 xx 个关系即发现存在矛盾（如A

Inconsistency found after x relations.

若根据这 m 个关系无法确定这 n 个元素的顺序，输出

Sorted sequence cannot be determined.

（提示：确定 nn 个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

输入输出样例

输入 #1复制

4 6
A 
输出 #1复制
 
Sorted sequence determined after 4 relations: ABCD.
 
解析：
 
这道题第一眼想到的就是先后顺序，这是可以想到拓扑排序。
 
注意:char(i+"A") != A这是我在测试是总过不了的。字符串和字符要分辨
 
#include
using namespace std;
const int N = 50;
struct Node {int u;int val;Node(int u = 0,int val = 0):u(u),val(val){}
};
vector vec[N];
int in[N];
set s1;
int in1[N];
int n, m,k,have,sum,ans;
vector vv;
void topu() {vv.clear();queue q;for (int i = 0; i < 26; i++) {if (in1[i] == 0 && s1.count(i)) {q.push(Node(i, 1));sum++;vv.push_back(char(i + 'A'));}}while (!q.empty()) {int u = q.front().u;int val = q.front().val;q.pop();for (int i = 0; i < vec[u].size(); i++) {int v = vec[u][i];in1[v]--;if (in1[v] == 0) {sum++;q.push(Node(v, val + 1));ans = max(ans, val + 1);vv.push_back(char(v + 'A'));}}}if (ans == n) {printf("Sorted sequence determined after %d relations: ", k);for (int i = 0; i < vv.size(); i++) {cout << vv[i];}cout << ".";exit(0);}else if(sum != have) {printf("Inconsistency found after %d relations.", k);exit(0);}
}
int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {string s;cin >> s;k = i;vec[s[0] - 'A'].push_back(s[2] - 'A');s1.insert(s[0] - 'A');s1.insert(s[2] - 'A');have = s1.size();in[s[2] - 'A']++;sum = 0;ans = 0;memcpy(in1, in, sizeof(in));topu();}printf("Sorted sequence cannot be determined.");return 0;
}