容易发现只要图中有非链部分则无解。剩下就非常简单了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),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 "; #else const char LL[]="%lld "; #endif n=read(),m=read(); for (int i=1;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+1,a+m+1); int t=unique(a+1,a+m+1)-a-1; for (int i=1;i<=n;i++) fa[i]=i; for (int i=1;i<=t;i++) if (find(a[i].x)==find(a[i].y)) {cout<<0;return 0;} else fa[find(a[i].x)]=find(a[i].y),degree[a[i].x]++,degree[a[i].y]++; int cnt=0; for (int i=1;i<=n;i++) if (degree[i]>2) {cout<<0;return 0;} else if (find(i)==i) cnt++; else size[find(i)]++; t=0; for (int i=1;i<=n;i++) if (find(i)==i&&size[i]) t++; int ans=1; for (int i=1;i<=t;i++) ans=(ans<<1)%P; for (int i=1;i<=cnt;i++) ans=1ll*ans*i%P; cout<<ans; return 0; }