bzoj3444: 最后的晚餐(并查集+组合数学)

3444: 最后的晚餐

题目：传送门

---

题解：

　　 考虑有解的情况：

　　 直接上并查集，同一个联通块里的人一定要坐在一起的。不难发现其实对于每个联通块最多就只有两种排列方式，那就直接把大于等于两个人的联通块先去做快速幂，然后直接看成cnt个数来全排列。

　　 对付无解的情况：

　　 1、不难想到，有环就无解。

　　 2、深入想想，一个人最多和两个暗恋对象坐在一起，那么如果一个人暗恋三个人或被三个人暗恋...那也无解

　　 3、最后一个有点坑，题目说没有自恋，但是没有说两情相悦不OK啊，那就要特判了ORZ

　　 吐槽：CC问我奇环合不合法...笑眯眯嘿嘿嘿，应该支持同性恋？？？

　　

---

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define mod 989381

 using namespace std;

 typedef long long LL;

 int n,m,x,y,fa[];

 int findfa(int x){if(fa[x]!=x)fa[x]=findfa(fa[x]);return fa[x];}

 LL p_m(LL a,int b)

 {

     LL ans=;

     while(b)

     {

         if(b%==)ans=ans*a%mod;

         a=a*a%mod;b/=;

     }

     return ans;

 }

 int d[],tot[];LL cnt;

 int mp[];

 int main()

 {

     memset(d,,sizeof(d));memset(mp,,sizeof(mp));

     scanf("%d%d",&n,&m);bool bk=true;

     for(int i=;i<=n;i++)fa[i]=i;

     for(int i=;i<=m;i++)

     {

         scanf("%d%d",&x,&y);if(mp[y]==x || mp[x]==y)continue;mp[x]=y;

         if(d[x]>= || d[y]>=){bk=false;break;}

         int fx=findfa(x),fy=findfa(y);

         if(fx!=fy)fa[fy]=fx;else {bk=false;break;}

         d[x]++;d[y]++;

     }

     cnt=;memset(tot,,sizeof(tot));LL k=;

     if(bk==false){printf("0\n");return ;}

     for(int i=;i<=n;i++)fa[i]=findfa(i);

     for(int i=;i<=n;i++)

     {

         if(fa[i]==i)cnt++;

         tot[fa[i]]++;

     }

     for(int i=;i<=n;i++)if(tot[i]==)k++;

     LL ans=p_m(,cnt-k);for(LL i=;i<=cnt;i++)ans=ans*i%mod;

     printf("%lld\n",ans);

     return ;

 }