解题思路
这个问题可以看作是一个图论中的链式关系计数问题。我们需要将n个同学排成一队,其中有些同学必须相邻且保持前后顺序。
核心思路:
-
将必须相邻的同学对视为一个整体(链),每个这样的链在最终排列中作为一个整体出现
-
使用并查集来维护这些链,将必须相邻的同学合并到同一个集合中
-
检查约束条件的合法性:
-
不能有循环依赖(如A在B前,B在A前)
-
每个同学最多只能有一个前驱和一个后继
-
-
最终答案:如果有k个链(包括单个同学的链),那么排列方式就是k!,因为每个链作为一个整体参与排列
代码注释:
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5 + 10,inf = 0x3f3f3f3f; int n,m,f[N],d[N]; int pre[N],nex[N]; // pre[i]: 必须在i前面的同学,nex[i]: 必须在i后面的同学// 并查集查找 int find(int x) {if(f[x] != x) f[x] = find(f[x]);return f[x]; }// 并查集合并 void merge(int x,int y) {int fx = find(x),fy = find(y);f[fy] = fx; }int main() {cin >> n >> m;for(int i = 1; i <= n; i++) f[i] = i; // 初始化并查集for(int i = 1; i <= m; i++){int x,y; cin >> x >> y;// 如果关系已经存在,跳过(避免重复处理)if(pre[y] == x || nex[x] == y) continue;// 合法性检查:如果y已经有前驱,或x已经有后继,或x和y已经在同一个链中(形成环)if(pre[y] != 0 || nex[x] != 0 || find(x) == find(y)){cout << 0; // 存在冲突,无解return 0;}merge(x,y); // 将x和y合并到同一个链中pre[y] = x; // 记录y的前驱是xnex[x] = y; // 记录x的后继是y }ll sum = 0,p = 1e9 + 7,ans = 1;// 统计有多少个独立的链(包括单个同学的链)for(int i = 1; i <= n; i++) {if(f[i] == i) sum++; // 并查集的根节点数量就是链的数量 }// 计算链的排列数:sum!for(int i = 1; i <= sum; i++){ans = ans * i % p;}cout << ans;return 0; }