【洛谷】P1347 排序

输出格式：
若根据前$x$个关系即可确定这$n$个元素的顺序yyy..y（如ABC），输出：
Sorted sequence determined after xxx relations: yyy...y.
若根据前$x$个关系即发现存在矛盾（如$A<B,B<C,C<A$），输出：
Inconsistency found after x relations.
若根据这$m$个关系无法确定这$n$个元素的顺序，输出：
Sorted sequence cannot be determined.
（提示：确定$n$个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

数据范围：
$2\le n\le 26,1\le m\le 600$。

思路是拓扑排序。首先要去除掉平行边的影响，此处用邻接矩阵存图，并且记录已经出现的所有点是哪些。每次多给一个不等式，就对已经出现过的点做拓扑排序，如果发现了环，则已经知道了有矛盾了，直接输出有矛盾；否则的话，说明对于已经给出的点而言是存在拓扑排序的，如果发现拓扑排序不唯一，则说明还需要继续读入不等式；如果发现拓扑序唯一，则看一下是否所有的$n$个点都排好，如果是，则说明已经找到了一个解；否则说明还需要继续读入不等式。代码如下：

#include 
#include 
#include 
using namespace std;

const int N = 30;
int n, m;
bool g[N][N];
int ind[N], ind1[N];
unordered_set<int> set;
int q[N];

int topsort() {
  // 将ind1复制给ind，因为本函数要修改入度ind
  memcpy(ind, ind1, sizeof ind);
  int hh = 0, tt = 0;
  // 只看已经出现的点
  for (int x : set)
    if (!ind[x]) q[tt++] = x;

  bool unique = true;
  while (hh < tt) {
    if (tt - hh > 1) unique = false;
    int u = q[hh++];
    for (int v = 1; v <= n; v++) {
      if (!g[u][v]) continue;
      ind[v]--;
      if (!ind[v]) q[tt++] = v;
    }
  }

  if (hh < set.size()) return 2;
  if (!unique || hh < n) return 0;
  return 1;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    string s;
    cin >> s;
    int x = s[0] - 'A' + 1, y = s[2] - 'A' + 1;
    if (!g[x][y]) {
      g[x][y] = true;
      ind1[y]++;
    }

    set.insert(x);
    set.insert(y);

    int res = topsort();
    if (!res) continue;
    if (res == 1) {
      printf("Sorted sequence determined after %d relations: ", i);
      for (int j = 0; j < n; j++) putchar(q[j] + 'A' - 1);
      puts(".");
    } else printf("Inconsistency found after %d relations.\n", i);

    exit(0);
  }

  puts("Sorted sequence cannot be determined.");
}
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

时间复杂度$O(mn)$，空间$O(n)$。