地址 https://www.acwing.com/problem/content/submission/345/
给定 nn 个变量和 mm 个不等式。其中 nn 小于等于26，变量分别用前 nn 的大写英文字母表示。
不等式之间具有传递性，即若 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的点 也就是说有两个起点 那么就不是唯一的排序关系
如果拓扑排序没有已经出现的点的数目 那么说明出现了环 也就是大小冲突了
代码如下
// 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 两个点之间的大小不明确
代码如下
1 // 111111.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
2 //
3
4 #include <iostream>
5 #include <vector>
6 #include <algorithm>
7 #include <queue>
8 #include <memory.h>
9 #include <string>
10
11 using namespace std;
12
13
14 const int N = 26;
15
16 int G[N][N];
17 int GCopy[N][N];
18
19 //入度计算
20 int D[N];
21
22 vector<int> ans;
23
24 int n, m;
25
26 void topsort()
27 {
28 queue<int> q;
29 ans.clear();
30 for (int i = 0; i < n; i++) {
31 if (D[i] == 0) q.push(i);
32 }
33
34 while (!q.empty()) {
35 int curr = q.front(); q.pop();
36 cout << char('A' + curr);
37
38 for (int i = 0; i < N; i++) {
39 if (G[curr][i] != 0) {
40 D[i]--;
41 if (D[i] == 0) q.push(i);
42 }
43 }
44
45 }
46
47
48 }
49
50 void floyd()
51 {
52 memcpy(GCopy, G, sizeof(G));
53 // 闭包传递 i到k k到j都成立 则i到j也成立
54 for (int i = 0; i < n; i++) {
55 for (int j = 0; j < n; j++) {
56 for (int k = 0; k < n; k++) {
57 GCopy[i][j] |= GCopy[i][k] && GCopy[k][j];
58 }
59 }
60 }
61 }
62
63 int Check()
64 {
65 for (int i = 0; i < n; i++) {
66 //有环 则说明冲突
67 if (GCopy[i][i] != 0)
68 return 2;
69 }
70
71 for (int i = 0; i < n; i++) {
72 for (int j = 0; j < i; j++) {
73 if (GCopy[i][j] == 0 && GCopy[j][i] == 0) {
74 //任意不相同两点 互相没有关联
75 //则说明当前输入还不足以说明n个点的大小排序
76 //还需要更多信息
77 return 0;
78 }
79 }
80 }
81
82 //异常情况排除了 则说明当前信息无冲突 且足以说明n个点的大小排序
83 return 1;
84 }
85
86
87 int main()
88 {
89 while (1) {
90 cin >> n >> m;
91 if (n == 0 || m == 0) break;
92 memset(D, 0, sizeof D);
93 memset(G, 0, sizeof(G));
94
95 int type = 0; int t = 0;
96
97 for (int i = 0; i < m; i++) {
98 string str;
99 cin >> str;
100
101 int a = str[0] - 'A';
102 int b = str[2] - 'A';
103
104 if (type == 0) {
105 G[a][b] ++;
106 D[b]++;
107 floyd();
108 type = Check();
109 if (type != 0) {
110 //有结果了 记录当前检测轮数
111 t = i + 1;
112 }
113 }
114 }
115
116
117 if (!type) puts("Sorted sequence cannot be determined.");
118 else if (type == 2) printf("Inconsistency found after %d relations.\n", t);
119 else {
120 printf("Sorted sequence determined after %d relations: ", t);
121 topsort();
122 /*for (int i = 0; i < ans.size(); i++) {
123 cout << char(ans[i] + 'A');
124 }*/
125 printf(".\n");
126 }
127
128
129 }
130
131
132 return 0;
133 }
View Code