[bzoj3444][并查集]最后的晚餐

2023-10-16 04:08

文章标签 查集 bzoj3444 晚餐

本文主要是介绍[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

Sample Output

8

HINT

【数据范围】

100%的数据，0＜n≤500000，1≤Ai，Bi≤n，0≤m≤n，保证没有人自恋。

题解

mmp辣鸡题毁我ac率
搞个并查集，暗恋的人就放在一个并查集里面。表示这个连通块里只能按顺序坐或者反过来坐一次
最后出来的一堆连通块，直接上全排列
那么对付无解的情况
无解就两种方案，第一种出现环了，第二种出现一个人暗恋了三个人
然而还有一种情况，比如a喜欢b同时b也喜欢a。那么这个环就不是无解的！！！

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL mod=989381;
int fa[510000];
int findfa(int x)
{if(fa[x]!=x)fa[x]=findfa(fa[x]);return fa[x];
}
LL pow_mod(LL a,int b)
{LL ans=1;while(b){if(b%2==1)ans=ans*a%mod;a=a*a%mod;b/=2;}return ans;
}
int n,m;
int T[510000],tt[510000];
int h[510000];
bool vis[510000];
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)fa[i]=i;bool bk=false;memset(vis,false,sizeof(vis));memset(T,0,sizeof(T));memset(tt,0,sizeof(tt));for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);if(tt[v]==u || tt[u]==v)continue;tt[u]=v;if(T[u]>=2 || T[v]>=2){bk=true;break;}int p=findfa(u),q=findfa(v);if(p!=q)fa[p]=q;else {bk=true;break;}T[u]++;T[v]++;}memset(h,0,sizeof(h));if(bk==true)printf("0\n");else{LL cnt=0,tmp=0;for(int i=1;i<=n;i++)fa[i]=findfa(i);for(int i=1;i<=n;i++){if(fa[i]==i)cnt++;h[fa[i]]++;}for(int i=1;i<=n;i++)if(h[i]==1)tmp++;LL ret=pow_mod(2,cnt-tmp);for(LL i=1;i<=cnt;i++)ret=ret*i%mod;printf("%lld\n",ret);}return 0;
}