题目描述
给定 n 个变量和 m 个不等式。其中 n 小于等于26，变量分别用前 n 的大写英文字母表示。
不等式之间具有传递性，即若 A>B 且 B>C ，则 A>C。
请从前往后遍历每对关系，每次遍历时判断：
如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序；
如果发生矛盾，则结束循环，输出有矛盾；
如果循环结束时没有发生上述两种情况，则输出无定解。
输入格式
输入包含多组测试数据。
每组测试数据，第一行包含两个整数n和m。
接下来m行，每行包含一个不等式，不等式全部为小于关系。
当输入一行0 0时，表示输入终止。
输出格式
每组数据输出一个占一行的结果。
结果可能为下列三种之一：
如果可以确定两两之间的关系，则输出 “Sorted sequence determined after t relations: yyy…y.”,其中’t’指迭代次数，’yyy…y’是指升序排列的所有变量。
如果有矛盾，则输出： “Inconsistency found after t relations.”，其中’t’指迭代次数。
如果没有矛盾，且不能确定两两之间的关系，则输出 “Sorted sequence cannot be determined.”。
数据范围
2≤n≤26，变量只可能为大写字母A~Z。
样例
输入样例1：
4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0
输出样例1：
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
输入样例2：
6 6
A<F
B<D
C<E
F<D
D<E
E<F
0 0
输出样例2：
Inconsistency found after 6 relations.
输入样例3：
5 5
A<B
B<C
C<D
D<E
E<A
0 0
输出样例3：
Sorted sequence determined after 4 relations: ABCDE
算法1
得到输入 的不等式关系 进行拓扑排序 任意时刻 如果两个入度为0的点 也就是说有两个起点 那么就不是唯一的排序关系
如果拓扑排序没有已经出现的点的数目 那么说明出现了环 也就是大小冲突了
C++ 代码
// 1111111111.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 26;
vector<vector<int>> G(N);
vector<int> D(N);
vector<int> letterTable(N);
vector<int> ans;
int n, m;
int topsort()
{
//拓扑排序
ans.clear();
vector<int> DCopy = D;
queue<int> q;
for (int i = 0; i < N; i++) {
if (DCopy[i] == 0&& letterTable[i] != 0)
q.push(i);
}
int flag = 0;
while (!q.empty()) {
//有同时两个进度为0 的 则说明 这两个点之间大小不明
if (q.size() > 1) {
flag = 1;
}
int curr = q.front(); q.pop();
ans.push_back(curr);
for (int i = 0; i < G[curr].size(); i++) {
int next = G[curr][i];
DCopy[next]--;
if (DCopy[next] == 0) {
q.push(next);
}
}
}
return flag;
}
int main()
{
while (1) {
cin >> n >> m;
if (n == 0 || 0 == m) break;
G.clear(); G.resize(N);
D.clear(); D.resize(N);
letterTable.clear(); letterTable.resize(N);
int letterCount = 0;
int r = 0;
int result = 0; int resultTurn = 0;
for (int i = 0; i < m; i++) {
string str;
cin >> str;
if (result != 0) continue;
int a = str[0] - 'A';
int b = str[2] - 'A';
if (letterTable[a] == 0) {
letterTable[a]++;
letterCount++;
}
if (letterTable[b] == 0) {
letterTable[b]++;
letterCount++;
}
//邻接表记录连边
G[a].push_back(b);
//b点入度加1
D[b]++;
r = topsort();
if (ans.size() != letterCount) {
result = -1; resultTurn = i + 1;
}else if (ans.size() == n && r == 0) {
result = 1;
//正确
resultTurn = i + 1;
}
}
if (result == -1) {
//有环 冲突
cout << "Inconsistency found after " << resultTurn << " relations." << endl;
}
else if (result == 1) {
cout << "Sorted sequence determined after " << resultTurn << " relations: ";
for (int i = 0; i < ans.size(); i++) {
cout << char('A' + ans[i]);
}
cout <<"."<< endl;
}
else if ( r == 1) {
//有同时两个进度为0 的 则说明 这两个点之间大小不明
cout << "Sorted sequence cannot be determined." << endl;
}
}
}
算法2
使用floyd进行闭包传递
如果a>c c >z 那么 a>z 在图中进行标记
每次获取信息后 进行检测 如果 g[i][i]有标记 那么就是出现了环
如果 g[i][j] g[j][i]都没有标记 那么说明 i j 两个点之间的大小不明确
C++ 代码
// 111111.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <string>
using namespace std;
const int N = 26;
int G[N][N];
int GCopy[N][N];
//入度计算
int D[N];
vector<int> ans;
int n, m;
void topsort()
{
queue<int> q;
ans.clear();
for (int i = 0; i < n; i++) {
if (D[i] == 0) q.push(i);
}
while (!q.empty()) {
int curr = q.front(); q.pop();
cout << char('A' + curr);
for (int i = 0; i < N; i++) {
if (G[curr][i] != 0) {
D[i]--;
if (D[i] == 0) q.push(i);
}
}
}
}
void floyd()
{
memcpy(GCopy, G, sizeof(G));
// 闭包传递 i到k k到j都成立 则i到j也成立
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
GCopy[i][j] |= GCopy[i][k] && GCopy[k][j];
}
}
}
}
int Check()
{
for (int i = 0; i < n; i++) {
//有环 则说明冲突
if (GCopy[i][i] != 0)
return 2;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (GCopy[i][j] == 0 && GCopy[j][i] == 0) {
//任意不相同两点 互相没有关联
//则说明当前输入还不足以说明n个点的大小排序
//还需要更多信息
return 0;
}
}
}
//异常情况排除了 则说明当前信息无冲突 且足以说明n个点的大小排序
return 1;
}
int main()
{
while (1) {
cin >> n >> m;
if (n == 0 || m == 0) break;
memset(D, 0, sizeof D);
memset(G, 0, sizeof(G));
int type = 0; int t = 0;
for (int i = 0; i < m; i++) {
string str;
cin >> str;
int a = str[0] - 'A';
int b = str[2] - 'A';
if (type == 0) {
G[a][b] ++;
D[b]++;
floyd();
type = Check();
if (type != 0) {
//有结果了 记录当前检测轮数
t = i + 1;
}
}
}
if (!type) puts("Sorted sequence cannot be determined.");
else if (type == 2) printf("Inconsistency found after %d relations.\n", t);
else {
printf("Sorted sequence determined after %d relations: ", t);
topsort();
/*for (int i = 0; i < ans.size(); i++) {
cout << char(ans[i] + 'A');
}*/
printf(".\n");
}
}
return 0;
}
赞👍我一想也是拓扑排序