[codeforces 859 E] Desk Disorder 解题报告（并查集+思维）

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

题目大意：

　　有$n$个人，$2n$个座位。

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

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

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

题解：

考虑把每个人看成边，把每个人想坐的位置连起来，显然我们会得到一个个的联通块

我们设某个联通块的边数为$e$，点数为$v$，那么有$e>=v-1$。

$e>v$的时候显然不存在这样的方案，不过数据好像保证了合法，就随意了

$e=v$时有$2$种方案。考虑环上的一条边（环的长度大于$1$），这条边的方法确定后其他边的放法都确定了

$e=v-1$是有$v$种方案，考虑枚举哪个点不选，其他的边的放法都确定了

考虑并查集维护联通块，对每个联通块记录下$siz$它的大小，$mark$表示这个块的种类（$0$表示没有环，$1$表示有自环，$2$表示有环但不是环）

当一个联通块有自环的时候方案肯定是固定的，写一个$unit$函数合并两个联通块即可

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

const int N=2e5+;

const int mod=1e9+;

int siz[N],mark[N],fa[N];

inline int read()

{

    char ch=getchar();

    int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();};

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

int find(int x)

{

    if (fa[x]!=x) fa[x]=find(fa[x]);

    return fa[x];

}

void unit(int a,int b)

{

    if (a==b)

    {

        mark[find(a)]=;//自环

        return;

    }

    a=find(a);b=find(b);

    if (a==b)

    {

        mark[a]=;//非自环的环

        return;

    }

    fa[a]=b;

    mark[b]|=mark[a];

    siz[b]+=siz[a];

}

int main()

{

    int n=read();

    for (int i=;i<=n*;i++) fa[i]=i,siz[i]=,mark[i]=;

    for (int i=,a,b;i<=n;i++)

    {

        a=read();b=read();

        unit(a,b);

    }

    ll ans=;

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

        if (fa[i]==i)

        {

            if (mark[i]==) ans=1ll*ans*siz[i]%mod;//没环就是树

            else if (mark[i]==) ans=ans*%mod;

        }

    printf("%lld\n",ans);

    return ;

}

巴特西

[codeforces 859 E] Desk Disorder 解题报告（并查集+思维）

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

题目大意：

题解：

最新文章

热门文章

巴特西

[codeforces 859 E] Desk Disorder 解题报告 （并查集+思维）

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

题目大意：

题解：

最新文章

热门文章

[codeforces 859 E] Desk Disorder 解题报告（并查集+思维）