CF859E Desk Disorder

传送门

Luogu

Solution

好好思考一下，发现人和座位构成的是一个二分图这还用想？

那么这个时候发现其实我们要求的就是这个二分图完全匹配的方案数，考虑在二分图上的一个连通块，如果是树，那么就是\(siz-1\)中方案，如果是一个环，就是\(2\)种，否则如果是环套环就是唯一的一种。直接并查集维护即可。

Code

/*
  mail: mleautomaton@foxmail.com
  author: MLEAutoMaton
  This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define REP(a,b,c) for(int a=b;a<=c;a++)
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi(){
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
const int N=200010,Mod=1e9+7;
int f[N],siz[N],n,cir[N],bl[N];
int find(int x){return f[x]==x?f[x]:f[x]=find(f[x]);}
int main(){
    n=gi();
    for(int i=1;i<=2*n;i++)f[i]=i,siz[i]=1;
    for(int i=1;i<=n;i++){
        int u=gi(),v=gi();
        if(u==v)bl[find(u)]=1;
        u=find(u);v=find(v);
        if(u!=v){
            cir[u]|=cir[v];
            f[v]=u;siz[u]+=siz[v];
            bl[u]|=bl[v];
        }
        else cir[u]=1;
    }
    int ans=1;
    for(int i=1;i<=2*n;i++)
        if(find(i)==i && !bl[i])
            if(cir[i])ans=2ll*ans%Mod;
            else ans=1ll*ans*siz[i]%Mod;
    printf("%d\n",ans);
    return 0;
}

CF859E Desk Disorder

原文：https://www.cnblogs.com/fexuile/p/11678963.html