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
Sample Output
8 【数据范围】 100%的数据，0＜n≤500000，1≤Ai，Bi≤n，0≤m≤n，保证没有人自恋。
把暗恋关系看作双向边，如果所有点度数都<=2，且没有环则有解。
否则不难发现每个连通分量是一条链，如果链上元素多于1则答案是2，否则答案是1。
每个连通分量肯定在一起，所以再将答案乘以连通分量个数的阶乘就行了。
#include#include #include #include #include #include #define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define ren for(int i=first[x];i;i=next[i])using namespace std;const int BufferSize=1<<16;char buffer[BufferSize],*head,*tail;inline char Getchar() { if(head==tail) { int l=fread(buffer,1,BufferSize,stdin); tail=(head=buffer)+l; } return *head++;}inline int read() { int x=0,f=1;char c=Getchar(); for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1; for(;isdigit(c);c=Getchar()) x=x*10+c-'0'; return x*f;}typedef long long ll;const int mod=989381;const int maxn=500010;int n,m,A[maxn],in[maxn],pa[maxn];int findset(int x) { return pa[x]==x?x:pa[x]=findset(pa[x]);}int main() { n=read();m=read(); rep(i,1,n) pa[i]=i; rep(i,1,m) { int u=read(),v=read(); if(A[v]==u) continue; if(findset(u)==findset(v)) {puts("0");return 0;} pa[findset(u)]=findset(v); in[v]++;in[u]++;A[u]=v; } int ok=1,blo=0; rep(i,1,n) { if(in[i]>2) ok=0; if(findset(i)==i) blo++; } if(!ok) puts("0"); else { ll ans=1,cnt=0; rep(i,1,blo) (ans*=i)%=mod; rep(i,1,n) if(!in[i]) cnt++; rep(i,1,blo-cnt) (ans*=2)%=mod; printf("%lld\n",ans); } return 0;}