BZOJ3444 最后的晚餐（并查集）

　　容易发现只要图中有非链部分则无解。剩下就非常简单了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

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

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 500010

#define P 989381

int n,m,fa[N],degree[N],size[N];

struct data

{

    int x,y;

    bool operator <(const data&a) const

    {

        return x<a.x||x==a.x&&y<a.y;

    }

    bool operator ==(const data&a) const

    {

        return x==a.x&&y==a.y;

    }

}a[N];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3444.in","r",stdin);

    freopen("bzoj3444.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

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

    {

        a[i].x=read(),a[i].y=read();

        if (a[i].x>a[i].y) swap(a[i].x,a[i].y);

    }

    sort(a+,a+m+);

    int t=unique(a+,a+m+)-a-;

    for (int i=;i<=n;i++) fa[i]=i;

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

    if (find(a[i].x)==find(a[i].y)) {cout<<;return ;}

    else fa[find(a[i].x)]=find(a[i].y),degree[a[i].x]++,degree[a[i].y]++;

    int cnt=;

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

    if (degree[i]>) {cout<<;return ;}

    else if (find(i)==i) cnt++;

    else size[find(i)]++;

    t=;

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

    if (find(i)==i&&size[i]) t++;

    int ans=;

    for (int i=;i<=t;i++) ans=(ans<<)%P;

    for (int i=;i<=cnt;i++) ans=1ll*ans*i%P;

    cout<<ans;

    return ;

}