343. 排序（ Floyd 处理传递闭包）

343. 排序 - AcWing题库

给定 n 个变量和 m 个不等式。其中 n 小于等于 26，变量分别用前 n 的大写英文字母表示。

不等式之间具有传递性，即若 A>B 且 B>C，则 A>C。

请从前往后遍历每对关系，每次遍历时判断：

• 如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序；
• 如果发生矛盾，则结束循环，输出有矛盾；
• 如果循环结束时没有发生上述两种情况，则输出无定解。

输入格式

输入包含多组测试数据。

每组测试数据，第一行包含两个整数 n 和 m。

接下来 m 行，每行包含一个不等式，不等式全部为小于关系。

当输入一行 0 0 时，表示输入终止。

输出格式

每组数据输出一个占一行的结果。

结果可能为下列三种之一：

1. 如果可以确定两两之间的关系，则输出 "Sorted sequence determined after t relations: yyy...y.",其中't'指迭代次数，'yyy...y'是指升序排列的所有变量。
2. 如果有矛盾，则输出： "Inconsistency found after t relations."，其中't'指迭代次数。
3. 如果没有矛盾，且不能确定两两之间的关系，则输出 "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.

解析： 

floyd求传递闭包应用。

本题实际上是求一个传递闭包。

可以将每对关系堪称一条有向边，同时通过Floyd算法求出最值，即没有入度的点，然后用类似拓扑排序的方式求出所有点。

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
const int N = 28;
int n, m;
bool g[N][N], d[N][N];
bool vis[N];void floyd() {memcpy(d, g, sizeof d);for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {d[i][j] |= d[i][k] && d[k][j];}}}
}int check() {for (int i = 0; i < n; i++) {if (d[i][i])return 2;}for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (!d[i][j] && !d[j][i])return 0;}}return 1;
}char get_min() {for (int i = 0; i < n; i++) {if (!vis[i]) {bool flg = 1;for (int j = 0; j < n; j++) {if (!vis[j] && d[j][i]) {flg = 0;break;}}if (flg) {vis[i] = 1;return i + 'A';}}}return 'Q';
}int main() {while (cin >> n >> m, n || m) {memset(g, 0, sizeof g);memset(vis, 0, sizeof vis);char op[5];int type=0, t;for (int i = 1; i <= m; i++) {cin >> op;int a = op[0] - 'A', b = op[2] - 'A';if (!type) {g[a][b] = 1;floyd();type = check();if (type)t = i;}}if (!type)cout << "Sorted sequence cannot be determined." << endl;else if (type == 2)printf("Inconsistency found after %d relations.\n", t);else {printf("Sorted sequence determined after %d relations: ", t);for (int i = 0; i < n; i++) {printf("%c", get_min());}cout <<"."<< endl;}}return 0;
}