对于原图，进行这样的简单操作：使用tarjan算法找出所有简单环
每找到一个环，就改变它的结构，从中任选一个点为该环的根
其它点连在这个点下面，环外和环右边相连的边不改变
这样每个环都变成只剩n - 1条边，最终能将这个仙人掌改造成一棵树
不妨将所有本来属于环上的点染成黑色，每一条新加的边可以对应成新树上的一条反向边
新加的边除了要满足仙人掌的性质，还要满足不能经过任何黑点之间的连边
此时这些黑点就将原树划分为一些连通块，只要统计每个块之间的答案，用乘法原理乘起来就行了
定义状态f[i]:以i为根的子树构成仙人掌的方案数
对于每一种最终合法的方案，只要其中存在一条边不在任何简单环上，
就增加一条它的重边，显然，这样仍然符合仙人掌的性质。
统计以x为根的子树的方案时，考虑每个儿子y，y向x连的这条边
这条边可以与另外一个儿子配对，或者和x的这条边配对
于是统计好子树答案，用乘法原理和组合数简单地转移就行了
注意当统计到某个连通块的根的时候，由于根向上的这条边不能用，是不能把根算进去的
原题好像是还需要特判无解的情况。。利用tarjan的性质搞搞就行啦
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #include<bitset> #define min(a,b) ((a) < (b) ? (a) : (b)) #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int maxn = 5E5 + 50; typedef long long LL; const LL mo = 998244353; int n,m,dfs_clock,Ans,dfn[maxn],low[maxn],f[maxn],h[maxn],Fac[maxn],Inv[maxn]; bool vis[maxn],Mark[maxn],Calc[maxn]; stack <int> s; vector <int> v[maxn],g[maxn]; inline int Mul(const LL &x,const LL &y) {return x * y % mo;} inline int Add(const int &x,const int &y) {return x + y < mo ? x + y : x + y - mo;} inline int C(const int &N,const int &M) {return Mul(Fac[N],Mul(Inv[M],Inv[N - M]));} int getint() { char ch = getchar(); int ret = 0; while (ch < '0' || '9' < ch) ch = getchar(); while ('0' <= ch && ch <= '9') ret = ret * 10 + ch - '0',ch = getchar(); return ret; } int ksm(int x,int y) { int ret = 1; for (; y; y >>= 1) { if (y & 1) ret = Mul(ret,x); x = Mul(x,x); } return ret; } bool Dfs1(int x,int from) { int cnt = 0; vis[x] = 1; dfn[x] = low[x] = ++dfs_clock; s.push(x); for (int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if (to == from) continue; if (!vis[to]) { if (!Dfs1(to,x)) return 0; if (low[to] == dfn[x]) { for (;;) { int k = s.top(); if (k == x) break; s.pop(); Calc[k] = Mark[k] = 1; g[x].push_back(k); } } else if (low[to] > dfn[x]) g[x].push_back(to),s.pop(); else low[x] = min(low[x],low[to]),++cnt; } else { if (dfn[to] < dfn[x]) ++cnt; low[x] = min(low[x],dfn[to]); } } return cnt < 2; } void Dfs2(int x) { int Son = 0,tot = 1; for (int i = 0; i < g[x].size(); i++) { int to = g[x][i]; Dfs2(to); if (Mark[to]) continue; ++Son; tot = Mul(tot,f[to]); } if (!Son) {f[x] = 1; return;} f[x] = 0; if (Calc[x]) { for (int i = 0; (i << 1) <= Son; i++) f[x] = Add(f[x],Mul(tot,Mul(C(Son,i << 1),h[i << 1]))); Ans = Mul(Ans,f[x]); } else { ++Son; for (int i = 0; (i << 1) <= Son; i++) f[x] = Add(f[x],Mul(tot,Mul(C(Son,i << 1),h[i << 1]))); } } void Solve() { n = getint(); m = getint(); while (m--) { int x = getint(),y = getint(); v[x].push_back(y); v[y].push_back(x); } if (!Dfs1(1,-1)) {puts("0"); return;} Ans = Calc[1] = 1; Dfs2(1); printf("%d\n",Ans); } void Clear() { for (int i = 1; i <= n; i++) { v[i].clear(),g[i].clear(); vis[i] = Mark[i] = Calc[i] = 0; } dfs_clock = 0; while (!s.empty()) s.pop(); } int main() { #ifdef DMC //freopen("ex_cactus2.in","r",stdin); freopen("DMC.txt","r",stdin); #endif int T = getint(); Fac[0] = h[0] = 1; for (int i = 1; i < maxn; i++) Fac[i] = Mul(Fac[i - 1],i); Inv[maxn - 1] = ksm(Fac[maxn - 1],mo - 2); for (int i = maxn - 2; i >= 0; i--) Inv[i] = Mul(Inv[i + 1],i + 1); for (int i = 2; i < maxn; i += 2) h[i] = Mul(h[i - 2],i - 1); while (T--) Solve(),Clear(); return 0; }