GESP 题解库 / 8 级题解 / [GESP202412 八级] 排队 · 第 11 / 24 题
GESP202412 八级 · P11380 · 中等

排队方案数:把相邻约束焊成块

"a 紧挨在 b 前面"会把两人焊成一条链;冲突或成环答案 0,否则答案 = 块数阶乘。

🧑
n ≤ 2 × 10⁵
同学数
🔗
m ≤ 2 × 10⁵
相邻关系数
⚡
O(n + m)
一次扫链判环
🎯
链合并 + k! mod 10⁹+7
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨所在班级共有 n 位同学,依次以 1, 2, …, n 标号。这 n 位同学想排成一行队伍,其中有些同学之间关系非常好,在队伍里需要排在相邻的位置。具体来说,有 m 对这样的关系(m 是一个非负整数)。当 m ≥ 1 时,第 i 对关系(1 ≤ i ≤ m)给出 aᵢ, bᵢ,表示排队时编号为 aᵢ 的同学需要排在编号为 bᵢ 的同学前面,并且两人在队伍中相邻。

现在小杨想知道总共有多少种排队方式。由于答案可能很大,你只需要求出答案对 10⁹ + 7 取模的结果。

输入输出样例

样例内容
输入 #14 2
1 3
2 4
输出 #12
输入 #23 0
输出 #26
输入 #33 2
1 2
2 1
输出 #30
💡
人话翻译:"a 排在 b 前面而且两人相邻"意味着 a、b 之间不能插任何人,顺序也不能反。
于是 a 和 b 就像被焊在了一起:一旦 1 → 3,队伍里就必然出现连续的一小段 …1, 3…。
顺着约束一路焊下去,同学们会被串成若干条链(块):4 2 / 1 3 / 2 4 就串成 [1, 3] 和 [2, 4] 两块。
接下来的结论很干净:每个块作为整体可以任意换位,所以有 k 个块时答案就是 k!(样例 1:2! = 2)。
但有两种情况会让答案变成 0:① 冲突——某人被要求有两个不同的后继(或两个不同的前驱);② 成环——像样例 3 的 1 → 2 → 1,两人互为首尾,谁也排不进去。

🔍 关键词提取

相邻约束链合并前驱 / 后继唯一性冲突判定判环阶乘取模

已知条件

项目说明
输入第一行 n, m;随后 m 行 aᵢ, bᵢ
输出一行一个整数:方案数对 10⁹ + 7 取模
数据范围1 ≤ n ≤ 2 × 10⁵,0 ≤ m ≤ 2 × 10⁵
关系含义a 必须排在 b 前面,并且两人相邻
部分分20%:n ≤ 8, m ≤ 10;20%:n ≤ 10³, m ≤ 1
特例m = 0 时答案就是 n!

需要解决的问题

02
思维导图
整理解题思路的全貌
🔗 相邻约束焊成链,答案 = 块数阶乘
📥 建模
nxt[a] = b:a 后面紧跟 b
pre[b] = a:b 前面是 a
一个人最多一个后继 / 前驱
重复的同一条约束视为一致
🚫 两类无解
冲突:同一人有两个不同后继
冲突:同一人有两个不同前驱
自环 a = a 当场判 0
成环:1 → 2 → 1 这类闭环
🔢 统计块数
pre = 0 的结点就是块头
块数 blocks = 块头个数
从块头顺 nxt 走,累计覆盖数 covered
covered < n ⇒ 有环 ⇒ 0
✅ 出答案
块内顺序唯一,块可整体换位
方案数 = blocks!
对 10⁹ + 7 取模
n ≥ 1 时 blocks ≥ 1
03
样例手算推导
三个样例 + 冲突与环的判定过程

🧮 样例 1:n = 4,约束 1 → 3、2 → 4

把每条约束翻译成 nxt / pre 两个数组:

约束含义nxt 变化pre 变化
1 31 后面紧跟 3nxt[1] = 3pre[3] = 1
2 42 后面紧跟 4nxt[2] = 4pre[4] = 2
1
第 1 步:找块头

块头 = 前面没有任何人的同学

pre[1] = 0 → 1 是块头

pre[2] = 0 → 2 是块头

pre[3] = 1、pre[4] = 2,都不是块头

块头有 2 个:1 和 2

2
第 2 步:顺着后继走,看覆盖了几个人

从 1 出发:1 → nxt[1] = 3 → nxt[3] = 0(停)

从 2 出发:2 → nxt[2] = 4 → nxt[4] = 0(停)

两条链:1 → 3(2 人)、2 → 4(2 人)

覆盖数 = 2 + 2 = 4

✅ 覆盖数 4 = n,没有环

3
第 3 步:数块数与方案数

块数 k = 块头个数 = 2

两块分别是 [1, 3] 和 [2, 4]

两种排法:1,3,2,4 与 2,4,1,3

k! = 2! = 2

✅ 答案 2

📊 两个块与两种排法

块成员块内顺序块能换位吗
A[1, 3]固定:1 必须在 3 前面且相邻能,整体搬
B[2, 4]固定:2 必须在 4 前面且相邻能,整体搬
🔑
把注意力从"人"换到"块":一旦看穿"块内顺序被锁死、只有块之间能换位",题目就退化成"把 k 个不同的东西排队",答案自然是 k!。
样例 2 的 3 0 正好是这个模型的极端情况:每人都自成一个块,k = 3,答案 3! = 6。

🧮 哪些输入答案必须是 0?

下面这张表把"无解"的四种情形一次讲清。

输入为什么无解答案
3 2 / 1 2 / 1 3同学 1 被要求有两个不同的后继(2 和 3)0
3 2 / 2 3 / 1 3同学 3 被要求有两个不同的前驱(2 和 1)0
3 2 / 1 2 / 2 1两人互为首尾成环,没有块头(样例 3)0
2 1 / 1 1自环:1 要排在自己前面还相邻0
1
样例 3:3 2 / 1 2 / 2 1 为什么是 0

constraint1:nxt[1] = 2、pre[2] = 1

constraint2:nxt[2] = 1、pre[1] = 2

两个数组都不冲突(每人恰好一个前驱、一个后继)

但 pre[1] = 2 ≠ 0,pre[2] = 1 ≠ 0

→ 一个块头也没有,覆盖数 = 0

✅ 覆盖数 0 ≠ n = 3,答案 0

2
另一种环:3 3 / 1 2 / 2 3 / 3 1

nxt:1→2、2→3、3→1

pre:pre[1]=3、pre[2]=1、pre[3]=2

同样没有任何 pre = 0 的点

从块头出发一个人也走不到

✅ 覆盖数 0 ≠ 3,答案 0

⚠️
只用"数块头"是不够的:样例 3 里 k = 0 个块,若天真地输出 0! = 1 就错了。
必须再做一步覆盖校验:从所有块头顺着 nxt 走下去,覆盖到的点数必须恰好等于 n。覆盖数不足 n,说明剩下的人全被锁在环里,答案只能是 0。
顺带一提:重复的同一条约束(例如两行都是 1 2)不算冲突,答案照常计算。
04
解法对比
前驱 / 后继链扫描 vs 并查集合并

⚔️ 解法对比

🟢 nxt / pre 双数组 + 顺链走一遍(推荐) 推荐

读数时就地判冲突,之后从每个块头顺 nxt 走到底,统计块数与覆盖数

  • 时间 O(n + m)
  • 空间 O(n)
  • 冲突判定在读数时完成
  • 判环只需一次线性扫描
💡
为什么它最稳:"块头顺链走一遍"天然同时给出两个信息——块数(走一次就发现一个块头)和覆盖数(链上一共数到多少人)。
覆盖数 = n 才合法,否则说明有环;这一个判断就替代了所有复杂的找环逻辑。

🔵 并查集合并 + 额外冲突判定

把每对 (a, b) union 起来,最后数连通块个数 k

  • 时间近似 O((n + m) α)
  • 也要单独写冲突判定(后继 / 前驱唯一性)
  • 重复的同一条约束必须特判,否则会误判成环
  • 思路直观,代码稍长
⚠️
两个容易踩的地方:① 并查集本身不检查冲突,"1 后面同时跟 2 和 3"这种输入它看不出来,必须另外用后继数组判;
② 完全相同的约束重复出现时,第二次 union 会发现两端已在同一个集合,如果直接当成环就会把正确答案误判成 0。

📈 性能对比

方案复杂度结论
nxt / pre 顺链走一遍O(n + m)✅ 推荐,判环最直接
并查集 + 独立冲突判定O((n + m) α)✅ 可行,细节略多
枚举所有 n! 种排列O(n! × m)❌ n ≤ 2 × 10⁵,不可行
05
算法流程图
读数判冲突 → 顺链统计 → 阶乘
开始读入 n、mnxt[1…n] = 0,pre[1…n] = 0,ok = true还有约束没读吗?读入一对 (a, b):要求 a 紧挨在 b 前面a 已有别的后继,或 b 已有别的前驱,或 a = b 吗?否 ✓nxt[a] = b,pre[b] = a是 ✗冲突,ok = false所有约束读完了吗?ok 为假吗?否 ✓继续统计块是 ✗直接输出 0从每个 pre = 0 的块头顺 nxt 走到底,统计块数 k 与覆盖数 cc 等于 n 吗?是 ✓答案 = k! mod 10⁹+7否 ✗存在环,答案 0输出答案读下一条约束
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧑 排队方案数计算器

第一行输入 n m,随后 m 行输入一对约束 a b(a 紧挨在 b 前面)。程序会展示每条约束的处理、焊成的块、冲突 / 环的判定与最终答案。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(链合并 + 判环 + 阶乘)

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

typedef long long ll;
const ll MOD = 1000000007;

int n, m;
int nxt[200005];     // nxt[a] = b 表示 a 后面必须紧挨着 b
int pre[200005];     // pre[b] = a 表示 b 前面必须是 a
bool vis[200005];

int main() {
    scanf("%d %d", &n, &m);

    bool ok = true;
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);

        // 冲突一:同一个人被要求有两个不同的后继 / 前驱
        if (nxt[a] != 0 && nxt[a] != b) ok = false;
        if (pre[b] != 0 && pre[b] != a) ok = false;
        // 冲突二:自环(自己排在自己前面还相邻)
        if (a == b) ok = false;

        nxt[a] = b;
        pre[b] = a;
    }
    if (!ok) { puts("0"); return 0; }

    // 从每个"没有前驱"的块头顺着 nxt 一路走到底
    int blocks = 0, covered = 0;
    for (int i = 1; i <= n; i++) {
        if (pre[i] != 0) continue;          // 有前驱 ⇒ 不是块头
        blocks++;                           // 发现一个新块
        int u = i;
        while (u != 0 && !vis[u]) {         // vis 防止在环里打转
            vis[u] = true;
            covered++;
            u = nxt[u];
        }
    }
    // 有环 ⇒ 环上的点永远走不到 ⇒ covered < n
    if (covered != n) { puts("0"); return 0; }

    // 块内顺序唯一,k 个块整体任意换位 ⇒ 方案数 = k!
    ll ans = 1;
    for (int i = 2; i <= blocks; i++) ans = ans * i % MOD;
    printf("%lld\n", ans);
    return 0;
}
🔑
三个要点:① 冲突要在读数过程中就地判掉(同一后继 / 同一前驱被抢占两遍);② 判环不要单独写找环,用"从块头走一遍,看覆盖数是否等于 n"最省事;③ 阶乘从 2 乘到 blocks,每一步都取模,防止溢出。

📖 关键几行怎么看

代码作用为什么这样写
if (nxt[a] != 0 && nxt[a] != b) ok = false;判冲突(后继)一个人只能有一个"必须紧跟自己的人";注意 nxt[a] == b 时说明是重复约束,不算冲突
if (pre[b] != 0 && pre[b] != a) ok = false;判冲突(前驱)对称地,一个人也只能有一个"必须紧挨在自己前面的人"
if (pre[i] != 0) continue;找块头前面没人的同学,一定是某条链的开头
while (u != 0 && !vis[u])顺链走沿着 nxt 走到底,同时用 vis 防死循环
if (covered != n) { puts("0"); return 0; }判环走不满 n 个人 ⇒ 有人被锁在环里 ⇒ 无解
ans = ans * i % MOD;算 k!块整体任意排列,乘法原理 + 边乘边取模
⚠️
五个坑:① 判出冲突后直接 return却没把剩下的输入读完——本题一次性读完整个输入,所以要么像本代码那样"读完再判",要么在循环里继续 scanf;② 把重复的同一条约束当成冲突(1 2 出现两次应当算一致);③ 只数块头、不做覆盖校验(样例 3 会被算成 0! = 1);④ 阶乘没取模或从 1 乘到 k 时漏乘;⑤ 数组越界——aᵢ, bᵢ 最大都是 n ≤ 2 × 10⁵,数组要开到 200005。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4 2
1 3
2 4
2题面样例 1:两个块,2! = 2
3 06题面样例 2:没有约束,3! = 6
3 2
1 2
2 1
0题面样例 3:成环,没有块头,答案 0
3 2
1 2
1 3
0冲突:同学 1 被要求有两个不同的后继
3 2
2 3
1 3
0冲突:同学 3 被要求有两个不同的前驱
5 3
1 2
2 3
3 4
2焊成一块 [1,2,3,4] 加一个孤立点 5,块数 2,2! = 2
2 1
1 1
0自环:自己排在自己前面还相邻,无解
2 2
1 2
1 2
1重复的同一条约束不算冲突,块数 1,1! = 1
1 01n = 1 无约束:只有 1 种排法
8 4
1 2
3 4
5 6
7 8
244 个块:4! = 24
✅
自查清单:① 冲突(两个后继 / 两个前驱 / 自环)判了吗?② 顺链走时统计了覆盖数吗?③ 覆盖数 ≠ n 时输出了 0 吗?④ 阶乘取模了吗?

🚨 易错点清单

⚠️
只数块头、不判环:样例 3(1 → 2 → 1)块头个数是 0,输出 0! = 1 就错了;必须校验覆盖数是否等于 n。
⚠️
把重复约束当冲突:同一条 a b 出现多次含义完全一样,不能判 0。
⚠️
冲突后没读完输入:若中途 return 又用逐行读入,残留数据会影响后续判断。
⚠️
阶乘忘记取模:k 最大 2 × 10⁵,k! 是天量数字,必须边乘边取模。
⚠️
数组开小:aᵢ, bᵢ 可达 n 的上限 2 × 10⁵。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n + m)
空间复杂度
O(n)
判冲突
读数时 O(1)
求阶乘
O(块数)

时间怎么算的?

空间都用在哪?

两个长度 n + 1 的整型数组 nxt、pre,一个 vis 标记数组,都是 O(n);不需要存下所有约束,边读边处理。

✅ 线性复杂度就能解决,核心不是算得慢不慢,而是把"相邻且有序"翻译成链、再把无解的两类情形彻底堵住。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「相邻约束 → 链 → 块排列」通用骨架
int nxt[N], pre[N];      // 后继 / 前驱(0 表示没有)
bool vis[N];

// 1) 读约束时判冲突:一个人只能有一个后继、一个前驱
if (nxt[a] && nxt[a] != b) ok = false;   // a 被要求跟两个人
if (pre[b] && pre[b] != a) ok = false;   // b 被要求跟两个人
if (a == b) ok = false;                  // 自环
nxt[a] = b; pre[b] = a;

// 2) 找块头(pre == 0),顺后继走一遍
//    块数 = 块头个数;覆盖数 = n 才合法(否则有环)
for (int i = 1; i <= n; i++) {
    if (pre[i]) continue;
    blocks++;
    for (int u = i; u && !vis[u]; u = nxt[u]) { vis[u] = true; covered++; }
}
if (covered != n) return puts("0"), 0;

// 3) 块内顺序唯一 ⇒ 只有块之间能换位 ⇒ 答案 = blocks!
ll ans = 1;
for (int i = 2; i <= blocks; i++) ans = ans * i % MOD;

// 经验:这类"把元素按约束打包成不可拆单元"的题
//   · 先想清楚"单元内部还有没有自由度"
//   · 再想清楚"单元之间怎么排列"
//   · 最后单独处理"约束互相矛盾"的无解情形

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
约束翻译成数组nxt[a] = b、pre[b] = a 两个数组刻画"紧挨"任何"相邻 + 有序"的排列约束题
就地判冲突读数时检查后继 / 前驱是否已被占用输入里带"互斥要求"的题(如每人只能匹配一个)
顺链走一遍判环走不满 n 个点 ⇒ 有环由"函数式图"(每个点出度 ≤ 1)判环的标准手法
打包成块 + 阶乘块内唯一、块间任意 → k!排列计数题里"固定段 + 自由段"的拆解思路
边乘边取模阶乘对 10⁹+7 取模所有计数取模题的基本功
🌟
思考题:如果把条件放宽成"a 必须排在 b 前面(不要求相邻)",答案还这么好算吗?(提示:这时候 a、b 不再被焊死,就变成了偏序计数问题——一般的偏序计数是困难的,但若每条链还是"直链"结构,可以用树形 DP / 组合数合并。回看本题,正是"相邻"这个额外条件把问题压缩成了简单的 k!。)