图论-floyed算法拓展-Acwing-343排序详解

 原题链接：343. 排序 - AcWing题库

整体思路

关系建模：使用邻接矩阵来表示变量之间的小于关系。若变量 A 小于变量 B，则在邻接矩阵中对应的位置置为 true。

传递闭包计算：借助 Floyd-Warshall 算法计算传递闭包，以此确定任意两个变量之间的关系。

状态检查：在每次添加新的不等式关系后，检查当前关系是否存在矛盾或者能否确定所有变量的顺序。

结果输出：依据检查结果输出相应信息，若能确定顺序则输出排序结果，若有矛盾则输出矛盾信息，若无法确定则输出无定解信息。

具体的解题解析已经在代码注释提到，这个题目解题思路挺有意思的，建议大家自己多练习几遍，bai~

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 26;
bool g[N][N], d[N][N];//g,d用来表示做传递闭包的过程，就是a<b,且b<c，那么将a,c之间就有关系且值为1 
bool st[N];//是否已经被访问 
int n, m;

// Floyd-Warshall算法，用于传递闭包
void floyed() {
    memcpy(d, g, sizeof d);//复制g,到d 
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] && d[k][j])//如果i<k且k<j，那么i<j为1 
                    d[i][j] = 1;
}

// 检查当前关系的状态
int check() {
    // 检查是否存在矛盾关系
    for (int i = 0; i < n; i++) if (d[i][i]) return 2;//如果自己i<i值为1，那肯定是矛盾了 
    // 检查是否所有元素都能确定顺序
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (!d[i][j] && !d[j][i])//如果i<j和j<i都没有关系，那么则不能确定关系 
                return 0;
    return 1;
}

// 获取当前未确定顺序的最小元素
char get_min() {
    for (int i = 0; i < n; i++) {
        if (!st[i]) {
            int flag = 1;
            for (int j = 0; j < n; j++) {
                if (!st[j] && d[j][i]) {//遍历没有被访问过且j<i的，如果没有的话那这个数就是最小的，因为没有小于它的数 
                    flag = 0;
                    break;
                }
            }
            if (flag) {
                st[i] = 1;//如果没有小于它的数，那标记已经被访问过 
                return 'A' + i;
            }
        }
    }
    // 避免编译警告，正常情况不会执行到这里
    return ' '; 
}

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 ch[5];
            scanf("%s", ch);
            int a = ch[0] - 'A';
            int b = ch[2] - 'A'; 
            if (!type) {
                g[a][b] = 1;
                floyed();
                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;
}