本文主要是介绍sdnu 1031 字母排序（拓扑排序的利用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：http://210.44.14.31/problem/show/1031
很明显是拓扑排序的利用。
注意事项：
1.记录下输入到第几个条件，产生矛盾或者已经排好序。
2.在有矛盾且M>=N-1的情况下，不能输出无法确定顺序。
代码如下（感觉写的不够简练，暂且这样了）：
#include<iostream>
#include<queue>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
vector<char>abc[27];
queue<char>sortabc;
int abcsum[27];
int main()
{int N, M;while (cin >> N >> M&&(N!=0||M!=0)){memset(abcsum, 0, sizeof(abcsum));string str;int key = 0; //记录下输入到第几个条件，产生矛盾或者已经排好序bool p = true; //记录是否有矛盾bool q = true; //记录是否已经排好序for (int h = 1; h <= M; h++){cin >> str;if (M < N - 1) continue; //要排好N个序列至少有N-1个条件if (str[0] >= 'a'&&str[0] <= 'z')str[0] -= 32;if (str[2] >= 'a'&&str[2] <= 'z')str[2] -= 32;if (str[1] == '<'){abc[str[0] - 'A'].push_back(str[2]);abcsum[str[2] - 'A']++;}else{abc[str[2] - 'A'].push_back(str[0]);abcsum[str[0] - 'A']++;}if (p){int tempabcsum[27];bool u=true; //当顺序无法确定时，标记一下while (!sortabc.empty())sortabc.pop();for (int i = 0; i < N; i++)tempabcsum[i] = abcsum[i];for (int i = 0; i < N; i++){int kk = -1;for (int j = 0; j < N; j++){if (tempabcsum[j] == 0){if (kk == -1) kk = j;else u = false;}}if (kk == -1){key = h;p = false;break;}tempabcsum[kk]--;sortabc.push(kk + 'A');for (unsigned int k = 0; k < abc[kk].size(); k++)tempabcsum[abc[kk][k] - 'A']--;}if (u&&q&&sortabc.size() == N){q = false;key = h;}}}if (!q&&sortabc.size() == N){cout << "Sorted sequence determined after " << key << " relations: ";while (!sortabc.empty()){cout << sortabc.front();sortabc.pop();}cout << "." << endl;}else if (!p){cout << "Inconsistency found after " << key << " relations." << endl;}else{cout << "Sorted sequence cannot be determined." << endl;}while (!sortabc.empty())sortabc.pop();for (int i = 0; i < 26; i++){while (!abc[i].empty()){abc[i].pop_back();}}}return 0;
}这篇关于sdnu 1031 字母排序（拓扑排序的利用）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
