Codeforces 859E Desk Disorder：并查集【两个属性二选一】

题目链接：http://codeforces.com/problemset/problem/859/E

题意：

　　有n个人，2n个座位。

　　给出这n个人初始的座位，和他们想坐的座位。

　　每个人要么坐在原来的位置不动，要么坐到想坐的座位上，但是不能有两个人坐在同一个座位上。

　　问你合法的安排座位的方案数。

题解：

　　将2n个座位抽象成2n个点。

　　对于每个人，从他的初始位置向想坐的位置连一条边。

　　总答案即为所有连通块答案的乘积。

　　由于每一个点最多向外连一条边，所以对于每一个连通块只有三种情况：

　　　　（1）是一棵树，根节点不自环，且所有边的方向都是由儿子指向父亲。

　　　　（2）是一棵树，根节点自环，且所有边的方向都是由儿子指向父亲。

　　　　（3）有且只有一个环。

　　对于这三种情况，可以发现：

　　　　（1）方案数 = 连通块大小siz[fa]

　　　　（2）方案数 = 1

　　　　（3）方案数 = 2

　　并查集维护一下，最后统计答案即可。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #define MAX_N 200005

 #define MOD 1000000007

 using namespace std;

 int n;

 int par[MAX_N];

 int siz[MAX_N];

 bool tag[MAX_N];

 bool loop[MAX_N];

 long long ans=;

 void init_union_find()

 {

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

     {

         par[i]=i;

         siz[i]=;

         tag[i]=false;

         loop[i]=false;

     }

 }

 int find(int x)

 {

     return par[x]==x ? x : par[x]=find(par[x]);

 }

 void unite(int x,int y)

 {

     int px=find(x);

     int py=find(y);

     if(px==py)

     {

         tag[px]=true;

         return;

     }

     siz[py]+=siz[px];

     tag[py]|=tag[px];

     par[px]=py;

 }

 void read()

 {

     cin>>n;

     init_union_find();

     int x,y;

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

     {

         cin>>x>>y;

         unite(x,y);

         if(x==y) loop[x]=true;

     }

 }

 void work()

 {

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

     {

         if(find(i)==i)

         {

             if(loop[i]) continue;

             if(tag[i]) ans=(ans<<1ll)%MOD;

             else ans=ans*siz[i]%MOD;

         }

     }

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     work();

 }

巴特西

Codeforces 859E Desk Disorder：并查集【两个属性二选一】

最新文章

热门文章