排队 题解

题目分析

有 $n$ 个同学排成一列，编号 $1 \sim n$。给出 $m$ 条关系，每条关系形如 $(a_i, b_i)$，表示 $a_i$ 必须恰好排在 $b_i$ 的前一位，两人相邻。要求计算满足所有关系的排队方案数，并对 $10^9+7$ 取模。

题目的约束相当于在若干同学之间建立了相邻且有序的绑定关系。由于每个关系要求两人必须相邻，且顺序固定，所以这些绑定关系会自然地连成若干条有向链。不同的链之间则可以任意排列。如果约束出现冲突（例如一个人必须同时与两个不同的人相邻，或者形成环路），则答案为 $0$。

解题思路

我们可以将每位同学看作一个点，每条关系 $(a,b)$ 是一条从 $a$ 指向 $b$ 的有向边，并且要求 $a$ 的右边恰好是 $b$。满足条件的排列等价于将这些点连成若干条有向链，且每条链内部的顺序被唯一确定。

因此，问题转化为：

1. 判定所有约束能否构成合法的若干条链：每个人最多只能有一个左邻居和一个右邻居，且不能形成环。
2. 统计最终的链的数量（孤立点也算长度为 $1$ 的链）。
3. 计算链的全排列数目：如果共有 $k$ 条链，则答案为 $k!$（阶乘），因为不同链之间可以任意交换位置，而每条链内部顺序唯一。

举个例子：若 $n=3$，约束为 $1 \to 2$，则形成一条链 $(1,2)$ 和一个孤立点 $3$，共 $2$ 条链，答案为 $2! = 2$（排列为 $[1,2,3]$ 和 $[3,1,2]$）。

算法说明

我们可以用并查集来维护哪些同学被连接在一起，同时用两个数组 r 和 l 分别记录每个同学的右邻居和左邻居。

具体步骤

1. 初始化并查集，每个点自成一个集合。
2. 遍历所有关系 $(a, b)$：
   • 冲突检测：
     • 如果 r[a] 已经存在且不等于 b，说明 $a$ 想同时有两个不同的右邻居，冲突。
     • 如果 l[b] 已经存在且不等于 a，说明 $b$ 想同时有两个不同的左邻居，冲突。
     • 如果 find(a) == find(b)，说明 $a$ 和 $b$ 已经在同一条链中，再加边就会形成环，冲突。
   • 若通过检测，则设定 r[a] = b，l[b] = a，并用并查集合并 $a$ 与 $b$。
3. 若中途出现冲突，直接输出 0 并结束程序。
4. 遍历 $1 \sim n$，统计并查集中根节点的数量，记为 $k$。
5. 输出 $k! \bmod (10^9+7)$。

正确性说明

• 每个同学至多一个左邻居和一个右邻居，保证连接后一定形成若干条直链，不会分叉。
• 并查集判环保证了链不会闭合。
• 这些链内部的顺序由有向边唯一确定（只能按链的方向排列），没有其他变化。
• 链之间是独立的，它们之间的相对顺序可以任意排列，故有 $k!$ 种方式。

时间复杂度分析

• 并查集操作：近乎 $O(m \cdot \alpha(n))$，其中 $\alpha$ 为反阿克曼函数，可视为常数。
• 最终统计与计算阶乘：$O(n)$。
• 总复杂度：$O(n + m)$，足以在 $n, m \le 2\times 10^5$ 的数据范围内通过。

空间复杂度：并查集数组与左右邻居数组均为 $O(n)$。

参考代码解释

cpp
复制
1#include <iostream>
2#include <cstring>
3#include <algorithm>
4
5using namespace std;
6
7const int N = 2e5 + 10, MOD = 1e9 + 7;
8
9typedef long long LL;
10
11int n, m;
12int p[N];        // 并查集父节点数组
13int l[N], r[N];  // l[i]：i的左邻居，r[i]：i的右邻居
14
15int find(int x)
16{
17    if (x != p[x])
18        p[x] = find(p[x]);
19    return p[x];
20}
21
22int main()
23{
24    cin >> n >> m;
25    
26    // 初始化并查集
27    for (int i = 1; i <= n; ++ i )
28        p[i] = i;
29    
30    while (m -- )
31    {
32        int a, b;
33        cin >> a >> b;
34        // 如果已经记录了相同的相邻关系，跳过
35        if (r[a] == b && l[b] == a)
36            continue;
37        // 冲突检查：a已存在不同右邻居 或 b已存在不同左邻居 或 形成环
38        if (r[a] || l[b] || find(a) == find(b))
39        {
40            cout << 0 << endl;
41            return 0;
42        }
43        // 记录相邻关系
44        r[a] = b, l[b] = a;
45        // 合并a和b所在的集合
46        a = find(a), b = find(b);
47        p[a] = b;
48    }
49    
50    int res = 1, k = 1;
51    // 统计根的数量k，并计算k的阶乘
52    for (int i = 1; i <= n; ++ i )
53        if (find(i) == i)
54            res = (LL)res * k ++ % MOD;
55    
56    cout << res << endl;
57    
58    return 0;
59}

代码细节解析

• r[a] == b && l[b] == a：当存在多条相同的约束时直接跳过，避免重复统计。
• 冲突判断：
  • r[a] 非零：说明 $a$ 之前已经指定了右邻居，且不是 $b$。
  • l[b] 非零：说明 $b$ 之前已经指定了左邻居，且不是 $a$。
  • find(a) == find(b)：说明 $a$ 和 $b$ 已经属于同一条链，再加边会形成环。
• 合并 a 和 b 时，要先取出根节点再合并，避免路径压缩对后续判断的影响（在本题中其实影响不大，但保持习惯）。
• 计算阶乘时，变量 k 从 $1$ 开始，每遇到一个根节点就乘以 k，然后 k 自增，从而算出 $k!$。注意使用 long long 类型防止乘法溢出。

总结

本题的核心是将“相邻且有序”的约束转化为有向链，利用并查集判环并检测每个节点的度数（左右邻居唯一性）。最终答案为链数的阶乘。这是并查集在图论建模中的一类典型应用，适合练习对约束条件的抽象与转化。