【BZOJ3444】最后的晚餐
Description
【问题背景】
高三的学长们就要离开学校，各奔东西了。某班n人在举行最后的离别晚餐时，饭店老板觉得十分纠结。因为有m名学生偷偷找他，要求和自己暗恋的同学坐在一起。
【问题描述】
饭店给这些同学提供了一个很长的桌子，除了两头的同学，每一个同学都与两个同学相邻（即坐成一排）。给出所有信息，满足所有人的要求，求安排的方案总数（这个数字可能很大，请输出方案总数取余989381的值，也可能为0）。
Input
输入有m+1行，第一行有两个用空格隔开的正整数n、m，如题所示。接下来的m行，每一行有两个用空格隔开的正整数，第i行为Ai和Bi，表示Ai的暗恋对象为Bi，保证Ai互不相等。
Output
输出只有一行，这一行只有一个数字，如题所示。
Sample Input
4 2
1 2
4 3
1 2
4 3
Sample Output
8
【数据范围】
100%的数据，0＜n≤500000，1≤Ai，Bi≤n，0≤m≤n，保证没有人自恋。
【数据范围】
100%的数据，0＜n≤500000，1≤Ai，Bi≤n，0≤m≤n，保证没有人自恋。
题解：如果方案不为0的话，最终的情况一定是形成若干个链和若干个单点。我们可以任意安排链和单点的排列顺序，并且每个链可以反向，所以答案就是（（链+单点）!*2^链）。
那什么情况是不合法的呢？1.有一个人的度数>2，这个记录一下度数就行。2.链中形成了环，这个可以用并查集。
注意a和b相互喜欢的情况！
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const ll P=989381;
const int maxn=500010;
int n,m;
int c1,c0;
int d[maxn],f[maxn],to[maxn];
ll ans;
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int find(int x)
{
return (f[x]==x)?x:f[x]=find(f[x]);
}
int main()
{
n=rd(),m=rd();
int i,a,b;
for(i=1;i<=n;i++) f[i]=i;
for(i=1;i<=m;i++)
{
a=rd(),b=rd(),to[a]=b;
if(to[b]==a) continue;
d[a]++,d[b]++;
if(find(a)==find(b))
{
printf("0");
return 0;
}
f[f[a]]=f[b];
}
for(i=1;i<=n;i++)
{
if(d[i]==1) c1++;
if(d[i]==0) c0++;
if(d[i]>2)
{
printf("0");
return 0;
}
}
c1>>=1,ans=1;
for(i=1;i<=c1+c0;i++) ans=ans*i%P;
for(i=1;i<=c1;i++) ans=(ans<<1)%P;
printf("%lld",ans);
return 0;
}