[2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16)]F False Intelligence
[2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest][Codeforces 883 E]Field of Wonders

[MemSQL Start[c]UP 3.0 - Round 1][Codeforces 859]E. Desk Disorder

Zarxdy34 posted @ 2017年10月21日 14:47 in Codeforces with tags 基环外向树 并查集 , 245 阅读

    题意:n个人和至多2n把椅子,每个人有现在正在坐的椅子和想要坐的椅子(可以相同)这两个椅子可选,一把椅子只能坐一个人,求方案数。

    题解:将椅子看成点,人看成边,构成联通块只有两种可能:一种是\(E=V-1\),即一棵树的情况;一种是\(E=V\),即基环外向树。其他的情况显然是无解的,而这道题肯定有解,所以只有这两种情况。另一种理解方法是,由于图联通,所以必有\(E>=V-1\);由于每个工程师至少能选择一把椅子,所以有\(E<=V\)。

    \(E=V-1\)时,该联通块为一棵树,方案数为V,因为树上只有一个点不会被选到,对每个没有选到的点方案唯一;\(E=V\)时,联通块上有环,环上的人只能选择全部坐在原位或者全部坐在想要坐的椅子上,方案数为2,环外的边方案唯一。一种特殊情况是一个人想要坐在自己正在坐的椅子上,此时方案数为1。

    具体实现就用并查集瞎搞搞就出来了。

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mo=1e9+7;

int head[maxn],nxt[maxn<<1],E[maxn<<1],Ecnt;
int n;
int ans;

void Add_Edge(int x,int y) {nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;}

int fa[maxn<<1];
int sz[maxn];
int v[maxn<<1];

int Find(int x) {return x==fa[x]?x:fa[x]=Find(fa[x]);}
void Union(int x,int y)
{
	int fx=Find(x),fy=Find(y);
	sz[fy]+=sz[fx];
	fa[fx]=fy;
}

int main()
{
	scanf("%d",&n);
	ans=1;
	for (int i=1,x,y;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		Add_Edge(x,y);
		fa[x]=x;
		fa[y]=y;
		sz[x]=sz[y]=1;
	}
	for (int x=1;x<=n*2;x++) if (sz[x])
	{
		for (int j=head[x];j;j=nxt[j])
		{
			int y=E[j];
			if (Find(x)==Find(y)) v[Find(y)]=max(v[Find(y)],1);
			if (x==y) v[Find(y)]=2;
			Union(x,y);
		}
	}
	for (int x=1;x<=2*n;x++) if (Find(x)==x)
	{
		if (v[x]==1) ans=ans*2%mo;
		if (v[x]==0) ans=(long long)ans*sz[x]%mo;
	}
	printf("%d\n",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter