题解：关于传递闭包及拓扑排序相关问题（两种算法对比）
一、题目背景
给定 (n) 个元素（用大写字母 (A) 到 (Z) 表示，即 (n) 最大为 (26)），以及 (m) 个关系（形如 (A < B) 表示 (A) 小于 (B)）。要求根据这些关系判断是否能确定元素之间的全序关系（即拓扑排序），或者是否存在矛盾关系（如 (A < B) 且 (B < A)）。
二、传递闭包算法（时间复杂度 (O(mn^3))）
（一）整体思路
- 初始化图的邻接矩阵 (g) 表示元素之间的直接关系，通过不断应用 Floyd 算法来计算传递闭包矩阵 (d)，从而得到元素之间的间接关系。
- 每次添加一个新关系后，重新计算传递闭包，并检查是否能确定全序关系或存在矛盾关系。
- 如果能确定全序关系，输出确定关系的步骤数以及排序后的序列；如果存在矛盾关系，输出矛盾出现的步骤数；如果无法确定全序关系，输出相应提示。
（二）代码逐段分析
- 头文件和全局变量
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 26;
int n, m;
bool g[N][N], d[N][N];
bool st[N];
- `#include <cstring>`：用于字符串操作和内存初始化函数，如 `memset`。
- `#include <iostream>`：提供 C++ 风格的输入输出流，如 `cin` 和 `cout`。
- `#include <algorithm>`：包含一些常用的算法函数，如 `min`、`max` 等。
- `using namespace std;`：使用标准命名空间，以便直接使用标准库中的函数和类型。
- `const int N = 26`：定义元素的最大数量（对应大写字母的数量）。
- `int n, m;`：`n` 表示元素的数量，`m` 表示关系的数量。
- `bool g[N][N], d[N][N];`：`g[i][j]` 表示元素 \(i\) 和元素 \(j\) 之间是否有直接关系（`true` 表示有，`false` 表示无）；`d[i][j]` 是传递闭包矩阵，用于存储元素 \(i\) 和元素 \(j\) 之间是否存在可达关系（通过传递得到的关系）。
- `bool st[N];`：`st[i]` 用于标记元素 \(i\) 是否已经在拓扑排序中被处理过。
floyd函数
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];
}
- `memcpy(d, g, sizeof d);`：将邻接矩阵 \(g\) 复制到传递闭包矩阵 \(d\) 中，作为初始状态。
- 三层循环实现 Floyd 算法：通过中间节点 \(k\)，更新任意两个节点 \(i\) 和 \(j\) 之间的可达关系。如果存在从 \(i\) 到 \(k\) 的关系且从 \(k\) 到 \(j\) 的关系，那么就存在从 \(i\) 到 \(j\) 的关系（`d[i][j] |= d[i][k] && d[k][j];`）。
check函数
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;
}
- 首先检查是否存在自环（即 \(d[i][i]\) 为 `true`），如果存在自环，说明存在矛盾关系，返回 \(2\)。
- 然后遍历所有节点对 \((i, j)\)（\(j < i\)），如果存在两个节点 \(i\) 和 \(j\) 之间既没有 \(i\) 到 \(j\) 的关系，也没有 \(j\) 到 \(i\) 的关系，说明无法确定全序关系，返回 \(0\)。
- 如果以上两种情况都不满足，说明可以确定全序关系，返回 \(1\)。
get_min函数
char get_min()
{
for (int i = 0; i < n; i ++ )
if (!st[i])
{
bool flag = true;
for (int j = 0; j < n; j ++ )
if (!st[j] && d[j][i])
{
flag = false;
break;
}
if (flag)
{
st[i] = true;
return 'A' + i;
}
}
}
- 遍历所有未被标记的元素 \(i\)：
- 对于每个元素 \(i\)，检查是否存在其他未被标记的元素 \(j\)，使得 \(j\) 到 \(i\) 存在关系（`d[j][i]` 为 `true`）。如果存在这样的 \(j\)，则 \(i\) 不是当前最小的元素，将 `flag` 设为 `false` 并跳出内层循环。
- 如果遍历完所有未被标记的元素后，`flag` 仍为 `true`，说明 \(i\) 是当前最小的元素，标记 \(i\) 为已处理（`st[i] = true;`），并返回对应的大写字母（`'A' + i`）。
main函数
int main()
{
while (cin >> n >> m, n || m)
{
memset(g, 0, sizeof g);
int type = 0, t;
for (int i = 1; i <= m; i ++ )
{
char str[5];
cin >> str;
int a = str[0] - 'A', b = str[2] - 'A';
if (!type)
{
g[a][b] = 1;
floyd();
type = check();
if (type) t = i;
}
}
if (!type) puts("Sorted sequence cannot be determined.");
else if (type == 2) printf("Inconsistency found after %d relations.\n", t);
else
{
memset(st, 0, sizeof st);
printf("Sorted sequence determined after %d relations: ", t);
for (int i = 0; i < n; i ++ ) printf("%c", get_min());
printf(".\n");
}
}
return 0;
}
- `while (cin >> n >> m, n || m)`：循环读取元素数量 \(n\) 和关系数量 \(m\)，当 \(n\) 和 \(m\) 都为 \(0\) 时结束循环。
- `memset(g, 0, sizeof g);`：初始化邻接矩阵 \(g\) 为全 `false`。
- 遍历每个关系：
- 读取关系字符串 `str`，解析出两个元素的编号 `a` 和 `b`。
- 如果还未确定全序关系或矛盾关系（`!type`），将关系添加到邻接矩阵 `g` 中（`g[a][b] = 1;`），然后调用 `floyd` 函数计算传递闭包，再调用 `check` 函数检查是否能确定全序关系或存在矛盾关系。如果能确定（`type` 不为 \(0\)），记录当前步骤数 `t = i`。
- 根据 `type` 的值输出相应结果：
- 如果 `type` 为 \(0\)，输出 `Sorted sequence cannot be determined.`。
- 如果 `type` 为 \(2\)，输出 `Inconsistency found after %d relations.`，其中 `%d` 为矛盾出现的步骤数 `t`。
- 如果 `type` 为 \(1\)，重置标记数组 `st`（`memset(st, 0, sizeof st);`），输出确定全序关系的步骤数，并调用 `get_min` 函数依次输出排序后的元素序列。
三、增量算法（时间复杂度 (O(mn^2))）
（一）整体思路
- 同样初始化图的关系矩阵 (d)，每次添加一个新关系后，通过增量更新的方式更新传递闭包矩阵 (d)，而不是像 Floyd 算法那样重新计算整个矩阵。
- 每次更新后检查是否能确定全序关系或存在矛盾关系。
- 最后根据检查结果输出相应信息，与传递闭包算法的输出逻辑类似。
（二）代码逐段分析
- 头文件和全局变量
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 26;
int n, m;
bool d[N][N];
bool st[N];
与传递闭包算法的头文件和部分全局变量相同，这里不再赘述。
2. check 函数和 get_min 函数
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 (!st[i])
{
bool flag = true;
for (int j = 0; j < n; j ++ )
if (!st[j] && d[j][i])
{
flag = false;
break;
}
if (flag)
{
st[i] = true;
return 'A' + i;
}
}
}
这两个函数的功能和实现与传递闭包算法中的同名函数完全相同，用于检查是否存在矛盾关系、确定全序关系以及获取当前最小元素。
3. main 函数
int main()
{
while (cin >> n >> m, n || m)
{
memset(d, 0, sizeof d);
int type = 0, t;
for (int i = 1; i <= m; i ++ )
{
char str[5];
cin >> str;
int a = str[0] - 'A', b = str[2] - 'A';
if (!type)
{
d[a][b] = 1;
for (int x = 0; x < n; x ++ )
{
if (d[x][a]) d[x][b] = 1;
if (d[b][x]) d[a][x] = 1;
for (int y = 0; y < n; y ++ )
if (d[x][a] && d[b][y])
d[x][y] = 1;
}
type = check();
if (type) t = i;
}
}
if (!type) puts("Sorted sequence cannot be determined.");
else if (type == 2) printf("Inconsistency found after %d relations.\n", t);
else
{
memset(st, 0, sizeof st);
printf("Sorted sequence determined after %d relations: ", t);
for (int i = 0; i < n; i ++ ) printf("%c", get_min());
printf(".\n");
}
}
return 0;
}
- `while (cin >> n >> m, n || m)`：循环读取输入，当 \(n\) 和 \(m\) 都为 \(0\) 时结束循环。
- `memset(d, 0, sizeof d);`：初始化关系矩阵 \(d\) 为全 `false`。
- 遍历每个关系：
- 读取关系字符串 `str`，解析出两个元素的编号 `a` 和 `b`。
- 如果还未确定全序关系或矛盾关系（`!type`），将关系添加到矩阵 \(d\) 中（`d[a][b] = 1;`），然后通过增量更新的方式更新传递闭包矩阵 \(d\)。具体来说，对于每个元素 \(x\)，如果 \(x\) 到 \(a\) 有关系，则 \(x\) 到 \(b\) 也有关系；如果 \(b\) 到 \(x\) 有关系，则 \(a\) 到 \(x\) 也有关系；对于任意两个元素 \(x\) 和 \(y\)，如果 \(x\) 到 \(a\) 有关系且 \(b\) 到 \(y\) 有关系，则 \(x\) 到 \(y\) 也有关系。
- 调用 `check` 函数检查是否能确定全序关系或存在矛盾关系，如果能确定（`type` 不为 \(0\)），记录当前步骤数 `t = i`。
- 根据 `type` 的值输出相应结果，与传递闭包算法的输出逻辑一致。
四、两种算法对比
- 时间复杂度：传递闭包算法使用 Floyd 算法计算传递闭包，时间复杂度为 (O(mn^3))，其中 (m) 是关系数量，(n) 是元素数量；增量算法通过增量更新传递闭包矩阵，时间复杂度为 (O(mn^2))。在关系数量 (m) 和元素数量 (n) 较大时，增量算法的时间效率更高。
- 空间复杂度：两种算法的空间复杂度主要取决于存储关系矩阵和标记数组的空间，均为 (O(n^2))（关系矩阵 (d[N][N]) 占用 (O(n^2)) 空间，标记数组 (st[N]) 占用 (O(n)) 空间，总体为 (O(n^2))）。
- 实现复杂度：传递闭包算法实现相对简单，直接应用 Floyd 算法计算传递闭包；增量算法在更新传递闭包矩阵时需要更细致的逻辑处理，但在处理大量关系时可能更高效。
