题解#1

分析：
关键性质：每条边至多属于一个简单环$→$这是一个仙人掌图（$Cactus Graph$）。
生成树计数：对于仙人掌图，每个简单环长为$k$，则生成树数为所有环长的乘积。
原因：每个环必须恰好删去一条边（$k$种选择），不同环的选择相互独立。
算法：用 Tarjan 找双连通分量（每个环是一个$biconnected component$），或用$DFS$检测环。对每个环统计边数$k$，答案为$\prod k \bmod 998244353$。
复杂度：$O(n + m)$。
代码：

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 100005;

int n, m;
vector<int> adj[MAXN];
int dfn[MAXN], low[MAXN], timer_;
long long ans = 1;

void tarjan(int u, int pe) {
    dfn[u] = low[u] = ++timer_;
    for (int e : adj[u]) {
        if (e == pe) continue;
        int v = (edges[e].first == u) ? edges[e].second : edges[e].first;
        if (!dfn[v]) {
            tarjan(v, e);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    // 统计以 u 为根的环
    for (int e : adj[u]) {
        if (e == pe) continue;
        int v = (edges[e].first == u) ? edges[e].second : edges[e].first;
        if (dfn[v] > dfn[u] && low[v] <= dfn[u]) {
            // v 在环中，环的边数 = 从 u 到 v 的路径边数 + 1
            // 需要更仔细处理
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    // 读边，建图
    // ...
    // 对每个环，ans = ans * k % MOD
    printf("%lld\n", ans);
    return 0;
}

实际上，更简单的方法是：仙人掌图中$m - n + 1 = 环的数量$，每个环独立贡献其长度。
更简单的方法（代码）：

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 100005;
const int MAXM = 100005;

int n, m;
int eu[MAXM], ev[MAXM];
vector<int> adj[MAXN];  // 存边id
int dfn[MAXN], low[MAXN], stk[MAXM], top, timer_;
bool inStk[MAXM];
long long ans = 1;

void tarjan(int u, int pe) {
    dfn[u] = low[u] = ++timer_;
    for (int e : adj[u]) {
        if (e == pe) continue;
        int v = eu[e] == u ? ev[e] : eu[e];
        if (!dfn[v]) {
            stk[++top] = e; inStk[e] = true;
            tarjan(v, e);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                // u 是割点，弹出构成一个 biconnected component
                int cnt = 0;
                while (true) {
                    int ee = stk[top--];
                    inStk[ee] = false;
                    cnt++;
                    if (ee == e) break;
                }
                if (cnt > 1) {
                    // 这是一个环（仙人掌图中双连通分量要么是单边，要么是环）
                    ans = ans * cnt % MOD;
                }
            }
        } else if (dfn[v] < dfn[u]) {
            stk[++top] = e; inStk[e] = true;
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &eu[i], &ev[i]);
        adj[eu[i]].push_back(i);
        adj[ev[i]].push_back(i);
    }
    tarjan(1, 0);
    printf("%lld\n", ans);
    return 0;
}

验证：

样例1：两个环（三角形$1\!-\!2\!-\!3\!-\!1$长度3，四边形$4\!-\!5\!-\!6\!-\!7\!-\!4$长度4），$3 \times 4 = 12 ✓$

样例2：无环，生成树唯一，答案$1 ✓$
注意：题目保证连通，从顶点 1 开始$Tarjan$即可。每条边至多属于一个环保证了每个双连通分量要么是单边、要么是简单环，因此弹出边数$>1$时即为环长