题解：P11380 [GESP202412 八级] 排队

· · 题解

解题思路

当 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;
}