排序

题目描述：

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

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

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

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

思路：

用floyed进行关系的传递，x<y则建一条x到y的边,按照如下的方式进行关系的传递

for(int k = 1; k <= n; ++k){
 for(int i = 1; i <= n; ++i){
     for(int j = 1; j <= n; ++j){
         dis[i][j] |= dis[i][k] & dis[k][j];
     }
 }
}

• 存在矛盾的条件是：dis[i][j] = dis[j][i] = 1 或者 dis[i][i] = 1，即出现i<j,j<i,或i<i
• 能结束的条件是：dis[i][j] = 1或者dis[j][i]=1，二者只能有一个是1，统计方法是记录n*n中1的个数为num，如果num * 2 + n == n则可以
• 不能确定所有变量的关系的条件是：dis[i][j]=dis[j][i]=0

所以我们可以边输入边，边跑floyed，每次跑都判断一下，如果跑到最后都不行，那就是无法确定所以变量的关系

坑点是：

• i < i
• 矛盾出现在确定关系后面则不算出现矛盾，而算能确定关系

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
char a, b;
int tr[30][30];
int dis[30][30];

void floyed(){
    for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)dis[i][j] = tr[i][j];
    for(int k = 1; k <= n; ++k){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                dis[i][j] |= dis[i][k] & dis[k][j];
            }
        }
    }
}

int check1(){
    floyed();
    int num = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(dis[i][j] == 1 && dis[j][i] == 1)return -1;
            if(dis[i][j] == 1)++num;
        }
    }
    if(num * 2 + n == n * n)return 1;
    return 0;
}

void work(){
    while (cin >> n >> m && (n + m)) {
        mem(tr, 0);
        bool ans = 0;
        for(int i = 1; i <= m; ++i){
            cin >> a >> b >> b;
            if(a == b){
                printf("Inconsistency found after %d relations.\n", i);
                ans = 1;
                for(int j = i + 1; j <= m; ++j)cin >> a >> a >> a;
                break;
            }
            tr[a - 'A' + 1][b - 'A' + 1] = 1;
            int p = check1();
            if(p == -1){
                printf("Inconsistency found after %d relations.\n", i);
                ans = 1;
                for(int j = i + 1; j <= m; ++j)cin >> a >> a >> a;
                break;
            }
            else if(p == 1){
                printf("Sorted sequence determined after %d relations: ", i);
                ans = 1;
                vector<pii>v;
                for(int i = 1; i <= n; ++i){
                    int num = 0;
                    for(int j = 1; j <= n; ++j){
                        if(dis[i][j])++num;
                    }
                    v.push_back(m_p(num, i - 1));
                }
                sort(v.begin(), v.end(), greater<pii>());
                for(auto [x, id] : v){
                    cout << (char)('A' + id);
                }
                cout << ".\n";
                for(int j = i + 1; j <= m; ++j)cin >> a >> a >> a;
                break;
            }
        }
        if(!ans)cout << "Sorted sequence cannot be determined." << endl;
    }
}


int main(){
    work();
    return 0;
}