题目描述

题目链接
有若干个字母，已知它们中某些字母之间的前后关系，求它们的排列顺序。

Input

输入数据包含若干组。
每组数据第一行两个整数N（2 <= N <= 26）、M，为字母的个数及已知条件的个数，字母为从A开始的N个字母。N、M均为0表示输入结束。
之后M行，为一个条件，格式为：字母<字母，或字母>字母，如A<B，代表A在B的前面，A>B代表A在B的后面。

Output

对于每组输入数据，输出包含一行，若确定了字母的顺序，则输出：
Sorted sequence determined after xxx relations: yyy…y.
若发现了矛盾，则输出：
Inconsistency found after xxx relations.
若无法确定全部字母的顺序，则输出：
Sorted sequence cannot be determined.
其中，xxx为已读入的条件的个数，yyy…y为排好序的字母序列。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
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

Sample Output

1
2
3
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

题解

初学拓扑， 一开始A了一道简单的题感觉自己要上天了，然后又在自己的oj里找了一题， 想爽一爽 ， 然后一落千丈， 哭叽。
好了， 咱们说思路。
由于这题让中途输出 第一次出现了问题的序号或者是在某个序号时， 排序就己经完成。 那就自觉的要想到在输入的时候就进行排序， 想法很好， 但是却有些无从下手。
注： 首先要明白当某时刻入度为0的结点的个数大于等于2时， 那就不能确定顺序。当个数小于0时， 就是出现了矛盾。
除了这些， 其他就好说了， 看代码来详细解释：

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//#include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include "algorithm"
#include "cstdio"
#include "queue"
#include "set"
#include "cstring"
#include "string"
#include "map"
#include "vector"
#include "math.h"
#include "utility"   // pair头文件
#define esp 1e-6
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<char, char>  P;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;
const int M = 1e9 + 5;

int vis[100], ma[100][100], in[100];
string s;
int n, m;

int topo(){   // 每加进一个条件就要拓扑一次
    s = ""; //拓扑序列， 要是加进某一个条件之后正好完成了此拓扑排序。 将其输出即可， 所以其为全局变量
    int now[100]; // 储存此时的所有边的入度
    memset(vis, 0, sizeof vis);
    int to = 0, f = 1, p; // to 入度为0的点的个数, f 标记这些字母是否完成了拓扑排序 
    // p 指向最后一个入度为0的点， 在下面可以看到， 
    for (int i = 1; i <= n; i++){
        now[i] = in[i]; // in 入度
    }
    for (int i = 1; i <= n; i++){
        to = 0; // 每一次循环都要找入度为0的点
        for (int j = 1; j <= n; j++){
            if (!now[j] && !vis[j]){ // 
                to++;
                p = j;
            }
        }
        if (to == 0)  //如果没有入度为0的点， 那就出现了矛盾
            return 0;

        if (to >= 2) // 大于等于两个就有多种情况。说明现在还未排好序， 所以标记个2
            f = 2;
        for (int i = 1; i <= n; i++){
            if (ma[p][i])
                now[i]--; // 正常套路， 让与p有关的边的入度减一
        }
        vis[p] = 1;
        s += p + 'A' - 1;
    }
    return f; // 返回1或2 具体看下

}

int main(){
    char a, b, f;
    while(cin >> n >> m) {
        if (!n && !m)
            break;
        memset(in, 0, sizeof in);
        int flag = 1;
        memset(ma, 0, sizeof ma);
        for (int i = 1; i <= m; i++){
            cin >> a >> f >> b;
            if(f == '>')
                swap(a, b);
            int x = a - 'A' + 1;  //这个处理技巧真的妙， 妙不可言
            int y = b - 'A' + 1;
            if (!ma[x][y]){
                ma[x][y] = 1;
                in[y]++;
            }
            x = topo(); // 这是返回值就排上用场了
            if (flag){ // 当flag == 0时， 代表着结果已出， 其他就没必要输出了
                if (x == 0){
                    flag = 0; // 标记flag  这个也很妙呀
                    printf("Inconsistency found after %d relations.\n", i);
                }
                else if (x == 1){
                    flag = 0;
                    printf("Sorted sequence determined after %d relations: ", i);
                    cout << s << ".\n";
                }
            }
        }
        if (flag)
            puts("Sorted sequence cannot be determined.");
    }
    return 0;
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan