P11380 [GESP202412 八级] 排队

发表于 更新于 分类于 ， ，

题目描述

小杨所在班级共有 nn 位同学，依次以 1,2,…,n1,2,\dots,n 标号。这 nn 位同学想排成一行队伍，其中有些同学之间关系非常好，在队伍里需要排在相邻的位置。具体来说，有 mm 对这样的关系（mm 是一个非负整数）。当 m≥1m\geq 1 时，第 ii 对关系（1≤i≤m1\leq i\leq m）给出 ai,bia_i,b_i，表示排队时编号为 aia_i 的同学需要排在编号为 bib_i 的同学前面，并且两人在队伍中相邻。

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

输入格式

第一行，两个整数 n,mn,m，分别表示同学们的数量与关系数量。

接下来 mm 行，每行两个整数 ai,bia_i,b_i，表示一对关系。

输出格式

一行，一个整数，表示答案对 109+710^9+7 取模的结果。

输入输出样例 #1

输入 #1

1
2
3
4 2
1 3
2 4

输出 #1

1
2

输入输出样例 #2

输入 #2

1
3 0

输出 #2

1
6

输入输出样例 #3

输入 #3

1
2
3
3 2
1 2
2 1

输出 #3

1
0

说明/提示

对于 20%20\% 的测试数据点，保证 1≤n≤81\leq n\leq 8，0≤m≤100\leq m\leq 10。

对于另外 20%20\% 的测试数据点，保证 1≤n≤1031\leq n\leq 10^3，0≤m≤10\leq m\leq 1。

对于所有测试数据点，保证 1≤n≤2×1051\leq n\leq 2\times 10^5，0≤m≤2×1050\leq m\leq 2\times 10^5。

答案

显而易见，对有关系的对象绑定为一个集合作为整体处理，其余求全排列即可。

对于冲突情况，分别有

  1. 关系中存在环
  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
#include <iostream>
using namespace std;

const int N = 2e5+1, MOD = 1e9+7;

int n, m, L[N], R[N], P[N];

int factorial(int x){  // 计算 x! 对 MOD 取模的结果
    int r = x;
    while(--x) r = (long long)r*x % MOD;
    return r;
}

int p(int n){  // 并查集找 n 的根
    return (P[n]==n) ? n : (P[n] = p(P[n]));
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    if(!m){ // 没有关系，直接全排列
        cout << factorial(n);
        return 0;
    }
    if(m==1){ // 只有一个关系，直接合并
        cout << factorial(n-1);
        return 0;
    }

    for(int i=1;i<=n;i++) P[i] = i;  // 初始化并查集

    while(m--){
        int l, r;
        cin >> l >> r;
        if(R[l]==r && L[r]==l) continue;  // 重复关系，直接忽略
        if(R[l] || L[r] || p(l)==p(r)){ // 有冲突，直接输出 0
            cout << 0;
            return 0;
        }
        R[l] = r;  // 合并关系
        L[r] = l;
        P[p(l)] = p(r);  // 合并并查集
    }

    int nx = 0;
    for(int i=1;i<=n;i++){
        if(p(i)==i) nx++;  // 统计独立的集合数量
    }

    cout << factorial(nx);  // 以集合为单位全排列
    return 0;
}