ZJOI2017 仙人掌

题目:

   如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

   现在九条可怜手上有一张无自环无重边的无向连通图,但是她觉得这张图中的边数太少了,
   所以她想要在图上连上一些新的边。同时为了方便的存储这张无向图,图中的边数又不能太多。经过权衡,她想要加边后得到的图为一棵仙人掌。
   不难发现合法的加边方案有很多,可怜想要知道总共有多少不同的加边方案。
   两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。

思路:

   先考虑树的情况。要把树变成一个仙人掌,可以在树上选择一些长度大于 的链,如果这些链不存在互相重叠的情况就是一种合法的方案。
   对于每个点,考虑它的所有连边的分配情况。选定某一条边,可以考虑不与任何边同一条链,或者选择每条边同一条链(不止有这两条,只是保证它们一定在同一条链中)。
   所以 ,一个棵树的方案数就是
   对于图的情况,如果本身满足仙人掌的限制,只要用 Tarjan 把每个环缩成点就行了。正确性也应该比较显然。复杂度

代码:

#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;
const int N = 5e5 + 5, M = 1e6 + 5, MOD = 998244353;

template<class T>
inline void rd(T &a) {
#define gc getchar()
    char c;
    bool f = false;
    for(c = gc; !isdigit(c); c = gc) f |= (c == '-');
    for(a = 0; isdigit(c); c = gc) a = (a << 1) + (a << 3) + c - '0';
    if(f) a = -a;
#undef gc
}

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {mset(HEAD, 0); tot = 0;}
    T& operator[] (int x) {return W[x];}
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
};
Link<N, M * 2, int> G, T;

int to[N], dfn[N], cur;
bool vis[N], no_ans;
int fa[N], edge_fa[N], edge_to[N];
void dfs_to(int o, int f) {
    vis[o] = true; to[o] = 0;
    dfn[o] = ++cur; fa[o] = f;
    erep(k, G, o) {
        int v = G[k];
        if(v == f) {
            edge_fa[o] = k;
            continue;
        }
        if(vis[v]) {
            if(dfn[v] < dfn[o]) {
                if(to[o]) no_ans = true;
                to[o] = v;
                edge_to[o] = k;
            }
            continue;
        }
        dfs_to(v, o);
    }
}

int val[N];
void dfs_chk(int o, int f) {
    erep(k, G, o) {
        int v = G[k];
        if(v == f || v == to[o] || to[v] == o) continue;
        dfs_chk(v, o);
        val[o] += val[v];
    }
    no_ans |= (val[o] > 1);
}

bool mark[M * 2];
#define rev(x) ((x) + (((x) & 1) ? 1 : -1))
void build(int n) {
    mset(mark, 0);
    rep(i, 1, n) {
        if(!to[i]) continue;
        mark[edge_to[i]] = true;
        mark[rev(edge_to[i])] = true;
        for(int j = i; j != to[i]; j = fa[j]) {
            mark[edge_fa[j]] = true;
            mark[rev(edge_fa[j])] = true;
        }
    }
    rep(i, 1, n) 
        erep(k, G, i) {
            int j = G[k];
            if(mark[k]) continue;
            T.add(i, j);
            // fprintf(stderr, "%d %d\n", i, j);
        }
}

int g[N], ans;
void dfs_ans(int o, int f) {
    vis[o] = true;
    int cnt = (f != 0);
    erep(k, T, o) {
        int v = T[k];
        if(v == f) continue;
        dfs_ans(v, o);
        cnt++;
    }
    ans = (ll) ans * g[cnt] % MOD;
}

int main() {
    File(cactus);
    int cas, n, m;
    g[0] = g[1] = 1;
    rep(i, 2, 5e5) g[i] = (g[i - 1] + (ll) g[i - 2] * (i - 1)) % MOD;
    rd(cas);
    while(cas--) {
        rd(n); rd(m);
        G.clear(); T.clear();
        rep(i, 1, m) {
            int u, v;
            rd(u); rd(v);
            G.add(u, v);
            G.add(v, u);
        }
        no_ans = false;
        rep(i, 1, n) vis[i] = false;
        dfs_to(1, 0);
        if(no_ans) {puts("0"); continue;}
        rep(i, 1, n) val[i] = 0;
        rep(i, 1, n)
            if(to[i]) {
                val[i]++;
                val[to[i]]--;
            }
        dfs_chk(1, 0);
        if(no_ans) {puts("0"); continue;}
        build(n);
        rep(i, 1, n) vis[i] = false;
        ans = 1;
        rep(i, 1, n) {
            if(vis[i]) continue;
            dfs_ans(i, 0);
        }
        printf("%d\n", ans);
    }
    return 0;
}