Luogu

LOJ

分析

首先特判原图不是仙人掌的情况，直接输出 $0$ 即可。

显然连边不会跨过一个环，因此可以直接断掉所有环边，则原图变为一个森林，方案数即为每棵树的方案数之积。

考虑如何计算一棵树的方案数。

我们假装一个边也是一条链，那么就相当于求用若干条不相交的链覆盖树上所有边的方案数。

考虑 DP。设 $dp_u$ 为 $u$ 子树中所有边加上父边被覆盖的方案数，$g_n$ 为一个点连出去 $n$ 条边都被覆盖的方案数。不难得到
$$
g_n=g_{n-1}+(n-1)g_{n-2}
$$

$$
dp_u=g_{deg_u}\times\prod_{v\in son_u}dp_v
$$

答案为 $dp_1$，冷静分析一下就是 $\prod g_{deg_i}$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;
const int mod=998244353;

int n,m,flag,g[N];

struct edge { int v,nxt; } e[N<<1];
int head[N],deg[N],cnt=0;
inline void addEdge(int u,int v) {
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int fa[N],in[N],dfn[N],tim=0;
inline void dfs(int u) {
    dfn[u]=++tim;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa[u]) continue;
        if (!dfn[v]) fa[v]=u,dfs(v);
        else if (dfn[v]>dfn[u]) {
            for (re int x=v;x!=u;x=fa[x]) {
                if (in[x]) { flag=1; return; }
                in[x]=1,deg[x]-=2;
            }
            deg[u]-=2;
        }
        if (flag) return;
    }
}

int main() {
    g[0]=g[1]=1;
    for (re int i=2;i<N;++i) g[i]=(g[i-1]+1ll*(i-1)*g[i-2])%mod;
    for (int T=read();T;--T) {
        n=read(),m=read();
        flag=cnt=0;
        for (re int i=1;i<=n;++i) head[i]=deg[i]=dfn[i]=in[i]=fa[i]=0;
        for (re int i=1;i<=m;++i) {
            int u=read(),v=read();
            addEdge(u,v),++deg[v];
            addEdge(v,u),++deg[u];
        }
        flag=0,dfs(1);
        if (flag) puts("0");
        else {
            int ans=1;
            for (re int i=1;i<=n;++i) ans=1ll*ans*g[deg[i]]%mod;
            printf("%d\n",ans);
        }
    }
    return 0;
}