题解：P11380 [GESP202412 八级] 排队

题目

小杨所在班级共有 位同学，依次以 标号。这 位同学想排成一行队伍，其中有些同学之间关系非常好，在队伍里需要排在相邻的位置。具体来说，有 对这样的关系（ 是一个非负整数）。当 时，第 对关系（）给出 ，表示排队时编号为 的同学需要排在编号为 的同学前面，并且两人在队伍中相邻。

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

对于所有测试数据点，保证 ，。

题解

现实中却是为了同学关系而把队列变成树，甚至完全图也有可能……

读题之后发现有两个点：

是否有解？

本人喜欢 Tarjan 和 数据结构，选用并查集喜欢关系。
本人喜欢 线性数据结构，选用链表维护相邻关系；

以下情况是不合法的：

• 在一个连通块内，说明出现了环；（并查集）
• 已经前驱了，否则会一对多；（链表）
• 已经后继了，否则会一对多；（链表）

注意判掉重边，重边是合法的。

解是多少？

对于每个连通块内其实是确定的，所以就是 。

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int MAXN = 200005;
const LL mod = 1e9+7;

int n, m;
LL res = 1;

int pre[MAXN];
int suf[MAXN];

int ancCnt;
int anc[MAXN];
inline void ancInit(int siz) {
    for (int i = 1; i <= siz; ++i)
        anc[i] = i;
    return;
}
inline int findAnc(int cur) {
    if (anc[cur] != cur)
        anc[cur] = findAnc(anc[cur]);
    return anc[cur];
}
inline void merge(int a, int b) {
    anc[findAnc(b)] = findAnc(a);
    return;
}

int main() {
    scanf("%d%d", &n, &m);
    ancInit(n);
    for (int i = 1; i <= m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (pre[b] == a && suf[a] == b)
            continue;
        int ancA = findAnc(a);
        int ancB = findAnc(b);
        if (ancA != ancB && !pre[b] && !suf[a]) {
            merge(a, b);
            suf[a] = b;
            pre[b] = a;
        } else
            cout << "0", exit(0);
    }
    for (int i = 1; i <= n; ++i)
        if (findAnc(i) == i)
            ancCnt++;
    for (int i = 1; i <= ancCnt; ++i)
        res = (res * i) % mod;
    cout << res;
    return 0;
}