P1347 [ECNA 2001] 排序 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1347，日期见页头。两边不一致时信原站。

题目描述

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

输入格式

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

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

输出格式

若根据前 x 个关系即可确定这 n 个元素的顺序 yyy..y（如 ABC），输出

Sorted sequence determined after x relations: yyy...y.

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

Inconsistency found after x relations.

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

Sorted sequence cannot be determined.

（提示：确定 n 个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

说明/提示

2 ≤ n ≤ 26，1 ≤ m ≤ 600。

输入输出样例

输入

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

输出

Sorted sequence determined after 4 relations: ABCD.

前 4 条关系已经把 ABCD 钉死了 ⇒ 在第 4 条就该停。

⚠⚠ 注意第 6 条又是 A<B（和第 1 条重复）—— 而程序在第 4 条就退出了， 这条重复的关系根本没被读进来。第 ⑤ 步会说这件事盖住了什么。

输入

3 2
A<B
B<A

输出

Inconsistency found after 2 relations.

A<B 和 B<A 成环 ⇒ 矛盾。

输入

26 1
A<Z

输出

Sorted sequence cannot be determined.

26 个元素只给了一条关系 ⇒ 顺序远远没定下来。 ★ 这一组专治「把「排得出来」当成「确定」」那个错法（第 ② 步）。

1★ 正解：每读进一条关系就重跑一次拓扑排序

n ≤ 26、m ≤ 600 ⇒ 每读一条重跑一次也只有约 m × (n + n²) = 42 万次，随便跑。

p1347.cpp★ 这一版就能 AC

// ★★ P1347 正解：**每读进一条关系就重跑一次拓扑排序**，判三种状态之一。
//
// 三种输出（逐字照题面）：
//   · 有矛盾（成环）        → `Inconsistency found after x relations.`
//   · 顺序已经完全确定      → `Sorted sequence determined after x relations: yyy...y.`
//   · m 条读完还不确定      → `Sorted sequence cannot be determined.`
//
// ★★★ 三处必须一个字一个字对的地方：
//   ① **判定的顺序**：先判矛盾（环），再判是否唯一 —— 一个有环的图排不出序，谈不上「确定」；
//   ② **一旦确定就立刻停止**（题面括号里那句提示：「确定 n 个元素的顺序后即可结束程序，
//      可以不用考虑确定顺序之后出现矛盾的情况」）—— 后面的关系一个都不许再读进图里；
//   ③ ★ **拓扑序唯一 ⟺ 每一步入度为 0 的点恰好只有一个**。
//      「排得出来」不等于「唯一」—— 这是本章那句「逼你想清楚拓扑序唯一是什么意思」的落点。
//
// ⚠ 而题面允许**重复的关系**（官方样例第一组里 `A<B` 就出现了两次）——
//   同一条边加两遍会让入度多算一次，**永远减不到 0** ⇒ 必须去重。解析页第 ④ 步量了这件事。
//
// 复杂度 O(m · (n + m))：n ≤ 26、m ≤ 600 ⇒ 至多约 4 × 10⁵ 次，随便跑。

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

int n, m;
bool has[26][26];                                     // has[u][v]：u < v 这条边在不在（★ 天然去重）

/* 返回 0 = 有环、1 = 唯一确定（顺序写进 out）、2 = 还不确定 */
static int topo(string& out) {
    int indeg[26] = {0};
    for (int u = 0; u < n; u++)
        for (int v = 0; v < n; v++) if (has[u][v]) indeg[v]++;
    vector<int> box;
    for (int i = 0; i < n; i++) if (!indeg[i]) box.push_back(i);
    bool uniq = true;
    out.clear();
    size_t head = 0;
    while (head < box.size()) {
        if ((int)box.size() - (int)head > 1) uniq = false;   // ③ 同时有两个可选 ⇒ 不唯一
        int u = box[head++];
        out += char('A' + u);
        for (int v = 0; v < n; v++)
            if (has[u][v] && --indeg[v] == 0) box.push_back(v);
    }
    if ((int)out.size() < n) return 0;                // 出不完 ⇒ 有环
    return uniq ? 1 : 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= m; i++) {
        string s;
        cin >> s;
        int u = s[0] - 'A', v = s[2] - 'A';
        has[u][v] = true;                             // ★ 重复的关系在这里被自然去重
        string ord;
        int r = topo(ord);
        if (r == 0) { printf("Inconsistency found after %d relations.\n", i); return 0; }   // ① 先判环
        if (r == 1) { printf("Sorted sequence determined after %d relations: %s.\n",
                             i, ord.c_str()); return 0; }                                   // ② 立刻停
    }
    printf("Sorted sequence cannot be determined.\n");
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 三处必须一个字一个字对的地方

判定的顺序：先判矛盾（有环），再判是否唯一。一个有环的图排不出完整序列，本来就谈不上「确定」。反过来写，有环时它会把一个残缺的序列当答案报出去（第 ③ 步）。
一旦确定就立刻停：题面括号里那句提示是硬约束 ——「可以不用考虑确定顺序之后出现矛盾的情况」。 ⇒ 确定之后，后面的关系一条都不许再读进图里（第 ④ 步）。
★★ 「拓扑序唯一」⟺ 每一步入度为 0 的点恰好只有一个。 这就是本章题单那句「逼你想清楚『拓扑序唯一』是什么意思」的落点 —— 「排得出来」只说明不矛盾，离「唯一」还差一整步。

2★★ 对拍的参照物：枚举 n! 个排列，逐字照题面的定义

p1347Brute.cpp参照物：枚举排列（300 轮不一致 0 轮）

题面那三句话，翻译成「有多少个排列满足前 i 条关系」：

题面说的	换个说法
矛盾	一个满足的排列都没有
确定	恰好一个
无法确定	两个或更多

⇒ ★★ 这份参照物一点图论都不用，和正解一行代码都不共享 —— 它把「拓扑序唯一」换成了一个不含「拓扑」二字的说法。本页所有数字都靠它撑着。

3⚠ 前两个错法，官方样例一测就死

p1347Uniq.cpp✗ 把「排得出来」当成「确定」

// ✗ P1347 错法五：**把「排得出来」当成了「顺序已经确定」**。
//
// 拓扑排序能跑完，只说明「不矛盾」；**能排出来的顺序可能有很多个**。
// 这一版一看队列没空、n 个点全出来了，就宣布「确定」——
// 于是官方样例第三组（`26 1 / A<Z`）它会当场报「确定」，而正确答案是「无法确定」。
//
// ⇒ ★★ 这就是本章题单那句「**逼你想清楚「拓扑序唯一」是什么意思**」的落点：
//   **唯一 ⟺ 每一步入度为 0 的点恰好只有一个。**

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

int n, m;
bool has[26][26];                                     // has[u][v]：u < v 这条边在不在（★ 天然去重）

/* 返回 0 = 有环、1 = 唯一确定（顺序写进 out）、2 = 还不确定 */
static int topo(string& out) {
    int indeg[26] = {0};
    for (int u = 0; u < n; u++)
        for (int v = 0; v < n; v++) if (has[u][v]) indeg[v]++;
    vector<int> box;
    for (int i = 0; i < n; i++) if (!indeg[i]) box.push_back(i);
    bool uniq = true;
    out.clear();
    size_t head = 0;
    while (head < box.size()) {
        /* ★ 少了这一句：if (box.size() - head > 1) uniq = false; */
        int u = box[head++];
        out += char('A' + u);
        for (int v = 0; v < n; v++)
            if (has[u][v] && --indeg[v] == 0) box.push_back(v);
    }
    if ((int)out.size() < n) return 0;                // 出不完 ⇒ 有环
    return uniq ? 1 : 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= m; i++) {
        string s;
        cin >> s;
        int u = s[0] - 'A', v = s[2] - 'A';
        has[u][v] = true;                             // ★ 重复的关系在这里被自然去重
        string ord;
        int r = topo(ord);
        if (r == 0) { printf("Inconsistency found after %d relations.\n", i); return 0; }   // ① 先判环
        if (r == 1) { printf("Sorted sequence determined after %d relations: %s.\n",
                             i, ord.c_str()); return 0; }                                   // ② 立刻停
    }
    printf("Sorted sequence cannot be determined.\n");
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

它在第三组样例上当场报 determined after 1 relations: ABCDEFGHIJKLMNOPQRSTUVWXYZ. —— 只给了一条 A<Z 就敢说定了。对拍 300 / 300 全被抓（每一轮都错）。

p1347Order.cpp✗ 先判唯一、后判环

第二组样例上它打出 determined after 2 relations: C. —— 一个长度只有 1 的「序列」。对拍被抓 59 / 300。

4★★ 后两个错法官方样例都放过了 —— 而它们各需要一档专门的数据

p1347NoStop.cpp✗ 确定之后没停，接着读

// ✗ P1347 错法三：**确定之后没有立刻停**，继续把后面的关系读进图里。
//
// 题面括号里那句提示写得很清楚：「确定 n 个元素的顺序后即可结束程序，
// **可以不用考虑确定顺序之后出现矛盾的情况**」。
// 这一版把答案记下来却接着读，于是后面的关系一旦造出环，它就改口报矛盾了。
//
// ⚠ 官方样例第一组挡不住它（第 4 条确定 ABCD，后两条 `B<D`、`A<B` 都不矛盾）——
//   要造一组「确定之后才矛盾」的数据才抓得到。解析页第 ⑤ 步就是这么造的。

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

int n, m;
bool has[26][26];                                     // has[u][v]：u < v 这条边在不在（★ 天然去重）

/* 返回 0 = 有环、1 = 唯一确定（顺序写进 out）、2 = 还不确定 */
static int topo(string& out) {
    int indeg[26] = {0};
    for (int u = 0; u < n; u++)
        for (int v = 0; v < n; v++) if (has[u][v]) indeg[v]++;
    vector<int> box;
    for (int i = 0; i < n; i++) if (!indeg[i]) box.push_back(i);
    bool uniq = true;
    out.clear();
    size_t head = 0;
    while (head < box.size()) {
        if ((int)box.size() - (int)head > 1) uniq = false;   // ③ 同时有两个可选 ⇒ 不唯一
        int u = box[head++];
        out += char('A' + u);
        for (int v = 0; v < n; v++)
            if (has[u][v] && --indeg[v] == 0) box.push_back(v);
    }
    if ((int)out.size() < n) return 0;                // 出不完 ⇒ 有环
    return uniq ? 1 : 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    int ansAt = -1;
    string ansOrd;
    for (int i = 1; i <= m; i++) {
        string s;
        cin >> s;
        int u = s[0] - 'A', v = s[2] - 'A';
        has[u][v] = true;                             // ★ 重复的关系在这里被自然去重
        string ord;
        int r = topo(ord);
        if (r == 0) { printf("Inconsistency found after %d relations.\n", i); return 0; }   // ① 先判环
        if (r == 1 && ansAt < 0) { ansAt = i; ansOrd = ord; }   // ★ 记下来，可是不停
    }
    if (ansAt > 0) {
        printf("Sorted sequence determined after %d relations: %s.\n", ansAt, ansOrd.c_str());
        return 0;
    }
    printf("Sorted sequence cannot be determined.\n");
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1347Dup.cpp✗ 边去了重，入度却没去重

// ✗ P1347 错法四：**边去了重，入度却没去重** —— 一半一半，最要命的那种。
//
// 很多人会这么写：用 `has[u][v]` 这张表存边（顺手就去重了），
// 可入度是**每读一条关系就 `indeg[v]++`** 的。于是重复的关系让入度多算了一次，
// 而出边只会把它减一次 ⇒ **那个点永远出不了队** ⇒ 程序误以为「有环」。
//
// ⚠⚠ 而**官方样例挡不住它**：第一组数据里 `A<B` 确实出现了两次（第 1 条和第 6 条），
//   可程序在第 4 条就已经「确定」并退出了 —— **那条重复的关系根本没被读进来。**
//   ⇒ ★ 又一次「样例把坑盖住了」，而这一次的盖法很特别：**程序提前退出，坑还没轮到出场。**
//
// ⚠⚠⚠ 顺带记一条被实测打回来的草稿：我一开始写的错法是「用 `vector` 存边、完全不去重」——
//   **那个根本不是 bug**。重边在 `g[u]` 里出现两次，出队时也就减两次，**自洽**。
//   ⇒ **「重边要不要去重」的答案是「看你两边是不是用同一套口径」，不是「一律要去重」。**

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

int n, m;
bool has[26][26];
int indegRaw[26];                                     // ★ 按「读进来几条」数，没去重

static int topo(string& out) {
    int indeg[26];
    for (int i = 0; i < n; i++) indeg[i] = indegRaw[i];
    vector<int> box;
    for (int i = 0; i < n; i++) if (!indeg[i]) box.push_back(i);
    bool uniq = true;
    out.clear();
    size_t head = 0;
    while (head < box.size()) {
        if ((int)box.size() - (int)head > 1) uniq = false;
        int u = box[head++];
        out += char('A' + u);
        for (int v = 0; v < n; v++)                   // ★ 出边是去过重的：只减一次
            if (has[u][v] && --indeg[v] == 0) box.push_back(v);
    }
    if ((int)out.size() < n) return 0;
    return uniq ? 1 : 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= m; i++) {
        string s;
        cin >> s;
        int u = s[0] - 'A', v = s[2] - 'A';
        has[u][v] = true;
        indegRaw[v]++;                                // ★ 每读一条就加，重复的加了两次
        string ord;
        int r = topo(ord);
        if (r == 0) { printf("Inconsistency found after %d relations.\n", i); return 0; }
        if (r == 1) { printf("Sorted sequence determined after %d relations: %s.\n",
                             i, ord.c_str()); return 0; }
    }
    printf("Sorted sequence cannot be determined.\n");
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 顺手随机抓不到，造对档就必抓

300 轮	顺手随机	专门造的那一档
确定之后没停	29	★ 300 / 300（「先钉死顺序、再补一条反的」）
边去重了、入度没去重	72	123（「关系一定有重复」，⚠ 那一档 234 轮很快就矛盾了）

★ 而「确定之后没停」那个 29 是有上界的：它只可能在「答案是确定」的轮次里被抓，而默认档 300 轮里三种结局是 矛盾 119 / 确定 44 / 不确定 137 —— 44 是它的天花板，实测 29。 ⇒ 又一次那条老规矩：抓获率对不上时，先数一数这一档里到底有多少轮问得出这个问题。

⚠⚠ 而「入度没去重」这个错法，是我的草稿被实测打回来之后重写的

草稿里我写的错法是「用 vector 存边、完全不去重」，理由听着很顺：重复的关系让入度多算一次，那个点就永远出不了队。

实测 300 轮抓到 0 次 —— 它根本不是 bug。 重边在 g[u] 里出现两次，u 出队时也就把 indeg[v] 减两次，自洽。

⇒ 真正会错的是半去重：用 has[u][v] 存边（顺手去了重），入度却按「读进来几条」数（没去重）—— 两边口径不一样，那个点才永远出不来。 ⇒ ★★ 「重边要不要去重」的答案不是「一律要去重」，是「看你两边是不是用同一套口径」。

5⚠ 官方样例第一组里那条重复的关系，被程序自己的提前退出盖住了

第一组样例是 4 6，第 6 条关系是 A<B —— 和第 1 条一模一样。可正确的程序在第 4 条就已经确定并退出了：


官方样例挡住了几个错法（共 5 个）	3 个（读完才判 / 判定顺序反了 / 不判唯一）
放过的两个	确定之后没停、入度没去重
★ 而「入度没去重」被放过的原因	★ 那条重复的关系根本没被读进来

⇒ ★★ 本书量过很多次「样例挡不挡得住」，这一次的盖法是新的： 不是数据凑巧、也不是那个 bug 概率低，而是程序在坑出现之前就退出了。 ⇒ 读样例时要顺手问一句：这组数据里，我的程序真的走到最后了吗？

6★ 对拍这一页

300 轮（`n` 随机 3~6，参照物 = 枚举排列）
正解 ≡ 枚举排列	★ 不一致 0 轮
不判唯一性（把「排得出来」当「确定」）	300
读完所有关系才判一次	133
判定顺序反了（先判唯一、后判环）	59
边去重、入度没去重	72 →（专门档）123
确定之后没停	29 →（专门档）★ 300
⚠ 这一档三种结局的分布	矛盾 119 / 确定 44 / 不确定 137

顶格 n = 26、m = 600：每读一条重跑一次拓扑 ⇒ 约 421 200 次，时限 1 秒，绰绰有余。

7度量程序和生成器

p1347Count.cpp度量程序（本页所有数字都出自它）

p1347Gen.cpp数据生成器

8一页纸


★★ 关键的一步	每读一条就重跑一次；先判环、再判唯一；一确定就立刻停
★★★ 「唯一」是什么意思	每一步入度为 0 的点恰好只有一个 —— 「排得出来」≠「唯一」（那个错法 300/300 被抓）
★★ 参照物	枚举 `n!` 个排列，逐字照题面：0 个满足 = 矛盾、1 个 = 确定、≥2 = 不确定
⚠ 样例挡住 3 个、放过 2 个	放过的是「确定后没停」和「入度没去重」
★★ 新的一种「样例盖住坑」	第一组里那条重复的关系排在第 6 位，程序第 4 条就退出了
⚠⚠ 草稿被打回	「完全不去重」不是 bug（重边减两次，自洽）；错的是半去重
★ 抓获率有天花板	「确定后没停」只能在「确定」那 44 轮里被抓，实测 29

洛谷 P1347 [ECNA 2001] 排序

0题目原文（本地存了一份）

输入

输出

输入

输出

输入

输出

1★ 正解：每读进一条关系就重跑一次拓扑排序

2★★ 对拍的参照物：枚举 n! 个排列，逐字照题面的定义

3⚠ 前两个错法，官方样例一测就死

4★★ 后两个错法官方样例都放过了 —— 而它们各需要一档专门的数据

5⚠ 官方样例第一组里那条重复的关系，被程序自己的提前退出盖住了

6★ 对拍这一页

7度量程序和生成器

8一页纸