3444: 最后的晚餐

3444: 最后的晚餐

https://www.lydsy.com/JudgeOnline/problem.php?id=3444

分析：

　　计数。

　　首先判断无解的情况，因为这是一张长桌子，所以出现了环无解，然后并查集判环。如果是两个人之间的环，可以跳过。因为每个人只能和两个人挨着，所以三个及三个以上都想和一个人挨着，那么无解。

　　然后就成了很多条序列，往一个大的序列上放，那么全排列为$A^n_n$，即n!。对于每个序列，它又有两种方法排列，（长度为1的只有一种），然后再乘以2。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int mod = 989381;
const int N = 500100;

int fa[N], du[N], cnt[N], L[N];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main() {
    
    int n = read(), m = read(), tot = 0;
    for (int i=1; i<=n; ++i) fa[i] = i;
    
    for (int t1,t2,i=1; i<=m; ++i) {
        int u = read(), v = read();
        if (u == L[v]) continue;

        if ((t1=find(u)) == (t2=find(v)) || du[u] >= 2 || du[v] >= 2) {
            puts("0");return 0;
        }
        
        L[u] = v;
        du[u] ++, du[v] ++; // du[t1]++ , du[t2]++
        fa[t1] = t2;
    }
    
    LL ans = 1;
    
    for (int i=1; i<=n; ++i) cnt[find(i)] ++;
    
    for (int i=1; i<=n; ++i) {
        if (cnt[i]) {
            if (cnt[i] > 1) ans = (ans * 2) % mod;
            tot ++;
        }
    }
    
    for (int i=1; i<=tot; ++i) ans = (ans * i) % mod;
    
    cout << ans;
    
    return 0;
}