P1347. 排序

发表于 分类于 阅读次数： Waline： 本文字数： 530 阅读时长 ≈ 2 分钟

考点

  • 拓扑排序

题解

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
#include <bits/stdc++.h>
using namespace std;
const int LEN = 26;
int n, m, tot, cnt, len, head[LEN], ind[LEN], tind[LEN], val[LEN];
string ans;
queue<int> q;

struct edge {
  int to_, nxt_;
} e[(int)600 + 50];

void add(int u, int v) {
  e[tot].nxt_ = head[u], e[tot].to_ = v;
  head[u] = tot++;
}

bool toposort() {
  for (int i = 0; i < n; ++i) {
    // 由于是在线建图，入度为0且有边的结点才纳入
    if (~head[i] && !tind[i]) {
      q.emplace(i);
      // 初始时路径长度为1，即本身
      val[i] = 1;
    }
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    ans += (char)(u + 'A');
    ++cnt;
    for (int i = head[u]; ~i; i = e[i].nxt_) {
      int v = e[i].to_;
      val[v] = max(val[v], val[u] + 1);
      if (--tind[v] == 0) q.emplace(v);
    }
  }
  for (int i = 0; i < n; ++i) len = max(len, val[i]);
  for (int i = 0; i < n; ++i)
    if (tind[i]) return false;
  return true;
}

int main() {
  // 链式前向星保存有向边
  memset(head, -1, sizeof(head));
  string in;
  int u, v;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    // 每次都要拓扑排序+找最长路，得初始化
    // len记录最长路径，cnt记录拓扑序列长度，ans记录答案
    len = cnt = 0, ans = "";
    memset(val, 0, sizeof(val));
    cin >> in, u = in[0] - 'A', v = in[2] - 'A';
    add(u, v), ++ind[v];
    copy(ind, ind + LEN, tind);
    // 初始化结束
    if (!toposort()) {
      cout << "Inconsistency found after " << i << " relations.";
      return 0;
    } else if (cnt == n && len == n) {
      cout << "Sorted sequence determined after " << i << " relations: " << ans
           << ".";
      return 0;
    }
  }
  if (cnt != n || len != n) cout << "Sorted sequence cannot be determined.";
  return 0;
}

思路

将题目抽象化，记A -> B为A < B，实际上是问所给条件能否构成A -> B -> C -> D

需要满足以下两个条件：

  • 不存在环路，A -> D时不可能存在D -> A
  • 图中的最长路长度等于元素个数n

所以步骤设计如下：

  1. 用链式前向星在线建图。因为结果要返回步骤数，不能选择离线
  2. 每次拓扑排序+寻找最长路，有以下三种情况：
    • 拓扑序列的元素个数、n、最长路长度三者相等，此时能确定整个数列的顺序
    • 边全部建完后，上述三者仍有不等的情况，说明无法确定
    • 拓扑序列的元素个数不等于n，说明存在环路，输出矛盾结果