自动搬运

查看原文

来自洛谷，原作者为

	FJ_EYoungOneC 这个人很勤快，但是他并不想留下什么

搬运于2025-08-24 23:06:52，当前版本为作者最后更新于2024-12-11 22:38:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

当 $m = 0$ 时，即求解 $n$ 个同学排队的方案数：$A_n^n$，即 $n!$。

当 $m = 1$ 时，我们可以使用捆绑法，将两个同学打包，变为一个同学，那么方案数为 $(n - 1)!$。

那么本题转换为，将有特殊需求的同学进行捆绑之后，剩余的同学数量。

那么如何对每一条关系做处理？假设 $a$ 要在 $b$ 前面，那么我们可以使用两个数组进行标记，$r_a = b$，$l_b = a$，表示 $a$ 的右边是 $b$，$b$ 的左边是 $a$。当出现 $a$ 在多个人前面，或者是 $b$ 在多个人后面，则直接输出 $0$。

接下来我们考虑如何处理成环的情况，如样例三所示，$1$ 要在 $2$ 前面，且 $2$ 要在 $1$ 前面，可以成功通过我们上述处理。考虑用并查集维护每一个特殊处理的区间，当 $a$ 与 $b$ 为同一个区间时，则直接输出 $0$。

另外本题特别坑的地方在于，某条建议可能重复出现，如下样例：

2 2
1 2
1 2

那么我们可以进行特判出现过的情况，若 $r_a = b$ 且 $l_b = a$，则表示一出现过该关系，即 continue。

最后，如何判断一个是一个小团体，还是一个人呢？

可以用并查集，若当前点的祖先为自己，则算做一个人，这样一个团体仅会被算一次。

AC_Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

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

typedef long long LL;

int n, m;
int p[N];
int l[N], r[N];

int find(int x)
{
    if (x != p[x])
        p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; ++ i )
        p[i] = i;
    
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        if (r[a] == b && l[b] == a)
            continue;
        if (r[a] || l[b] || find(a) == find(b))
        {
            cout << 0 << endl;
            return 0;
        }
        r[a] = b, l[b] = a;
        a = find(a), b = find(b);
        p[a] = b;
    }
    
    int res = 1, k = 1;
    for (int i = 1; i <= n; ++ i )
        if (find(i) == i)
            res = (LL)res * k ++ % MOD;
    
    cout << res << endl;
    
    return 0;
}