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

    题意：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;
}