排序-拓扑排序


排序

题目描述

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列,例如,一个有序的数列 A,B,C,DA,B,C,D 表示 A<B,B<C,C<DA<B,B<C,C<D。在这道题中,我们将给你一系列形如 A<BA<B 的关系,并要求你判断是否能够根据这些关系确定这个数列的顺序。


输入

第一行有两个整数 n,m。n 表示需要排序的元素数量,第 1 到 n 个元素将用大写的 A,B,C,D….表示。m 表示将给出的形如 A<B 的关系的数量。

接下来有 m 行,每行有 3 个字符,分别为一个大写字母,一个 < 符号,一个大写字母,表示两个元素之间的关系。

输出

若根据前 x 个关系即可确定这 n 个元素的顺序 yyy..yyyy..y(如ABC),输出

Sorted sequence determined after xxx relations: yyy…y.

若根据前 x 个关系即发现存在矛盾(如 A<B,B<C,C<A),输出

Inconsistency found after xxx relations.

若根据这 m 个关系无法确定这 n 个元素的顺序,输出

Sorted sequence cannot be determined.

(提示:确定 n 个元素的顺序后即可结束程序,可以不用考虑确定顺序之后出现矛盾的情况)


样例输入

4 6
A<B
A<C
B<C
C<D
B<D
A<B

样例输出

Sorted sequence determined after 4 relations: ABCD.

样例输入2

3 2
A<B
B<A

样例输出2

Inconsistency found after 2 relations.

样例输入3

26 1
A<Z

样例输出3

Sorted sequence cannot be determined.

数据规模与约定

时间限制:1 s

内存限制:256 M

100% 的数据保证 2≤n≤26

思路

  • 本题考查点:判断图是否有环、判断这个图的拓扑排序是否唯一

  • 对于这种中途可以结束程序的题目,只能一边输入一边进行拓扑排序了

代码演示

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, rudu[27], cnt;

char ans[27];
int q[27], l, r;

vector <vector <int> > edge(27, vector<int>() );
inline int Topological_sorting() {
    cnt = 0, l = 0, r = 0;
    int in[27], qcnt = 0;
    for (int i = 0; i < n; i++) {
        in[i] = rudu[i];
        if (in[i] == 0) q[r++] = i;
    }
    
    while (l < r) { //队列中元素始终不唯一代表拓扑序列不唯一,始终为1代表拓扑序列唯一 
        qcnt = max(qcnt, (r - l));
        int tp = q[l++];
        ans[cnt++] = tp + 'A';
        for (auto to : edge[tp]) {
            if (--in[to] == 0) {
                q[r++] = to;
            }
        }
    }
    if (cnt < n) return 1; //有环 
    if (qcnt == 1) return 2; // 拓扑排序序列唯一 
    return 0;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        char a, b;
        getchar();
        scanf("%c<%c", &a, &b);
        rudu[b - 'A']++;
        edge[a - 'A'].push_back(b - 'A');
        int x = Topological_sorting();
        if (x == 2) {
            printf("Sorted sequence determined after %d relations: %s.\n", i, ans);
            return 0;
        } else if (x == 1) {
            printf("Inconsistency found after %d relations.\n", i);
            return 0;
        }
    }
    printf("Sorted sequence cannot be determined.\n");
    
    return 0;
}

文章作者: Axieyun
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Axieyun !
评论
评论
  目录