G8023 [GESP202609 八级] 生成树计数 题解

知识点：仙人掌图、深度优先搜索、组合计数。

解题思路

图为仙人掌，每个简单环必须且只需删去一条边，桥全部保留，答案为所有环长度的乘积。用显式栈DFS，对指向祖先的非父边计算深度差+1为环长。

为什么正确

每条边至多属于一个环，各环删边选择独立；任意这样删边后连通且无环，生成树与这些选择一一对应。

易错点

按边编号跳过父边，避免把无向反向边当成环；同一环只在从深点回祖先方向统计一次，模998244353。

复杂度

时间O(n+m)，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int>>>g(n+1);
    for(int i=0;i<m;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back({v,i});
        g[v].push_back({u,i});
    }
    vector<int>dep(n+1,-1),parentedge(n+1,-1),idx(n+1);
    dep[1]=0;
    vector<int>st= {
        1
    }
    ;
    long long ans=1;
    while(!st.empty()) {
        int u=st.back();
        if(idx[u]==(int)g[u].size()) {
            st.pop_back();
            continue;
        }
        auto [v,id]=g[u][idx[u]++];
        if(id==parentedge[u])continue;
        if(dep[v]<0) {
            dep[v]=dep[u]+1;
            parentedge[v]=id;
            st.push_back(v);
        }
        else if(dep[v]<dep[u])ans=ans*(dep[u]-dep[v]+1)%998244353;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用16个自行生成的测试点。