P6790 题解

DaiRuiChen007 · 2023-11-16 21:41:05 · 题解

P6790 题解

题目大意

给一张 n 个点 m 条边的图，保证存在某种保留 m-1 条边的方案使得新图是边仙人掌，求图的生成树个数。

数据范围：n,m\le 5\times 10^5。

思路分析

注意到原图环很少，因此考虑证明原图是广义串并联图，任取四个点，容易发现无法选出六条边不交的路径将他们两两连接，因此原图是广义串并联图。

考虑用广义串并联图方法逐步简化这张图（删一度点、缩二度点、叠合重边）。

观察广义串并联图缩边后的一条边 u\to v，显然对应原图的一个子图，且子图里的点除了 u\to v 以外只和 u/v 连接，因此这个子图最后的状态只有两种：u,v 连通或 u,v 不连通。

不妨设 e=(u,v) 连通方案数为 f(e)，不连通方案数为 g(e)。

• 删一度点：答案乘上 f(e)。
• 缩二度点：合并 e_1,e_2 得到 f(e^*)=f(e_1)\times f(e_2),g(e^*)=f(e_1)\times g(e_2)+f(e_2)\times g(e_1)。
• 叠合重边：合并 e_1,e_2 得到 f(e^*)=f(e_1)\times g(e_2)+f(e_2)\times g(e_1),g(e^*)=g(e_1)\times g(e_2)。

用队列维护度数 \le 2 的点，逐步 BFS 即可。

时间复杂度 \mathcal O(n\log n)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int MAXN=5e5+5,MOD=998244353;
int n,m;
map <int,array<ll,2>> g[MAXN];
queue <int> Q;
ll ans=1;
inline void link(int u,int v,array<ll,2> x) {
    if(g[u].count(v)) {
        array<ll,2> y=g[u][v];
        g[u][v]=g[v][u]={x[0]*y[0]%MOD,(x[0]*y[1]+x[1]*y[0])%MOD};
    } else g[u][v]=g[v][u]=x;
}
inline void upd(int x) { if(g[x].size()<=2) Q.push(x); }
signed main() {
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),link(u,v,{1,1});
    for(int i=1;i<=n;++i) upd(i);
    while(Q.size()) {
        int u=Q.front(); Q.pop();
        if(g[u].size()==1) ans=ans*(g[u].begin()->se)[1]%MOD;
        if(g[u].size()==2) {
            int x=g[u].begin()->fi,y=g[u].rbegin()->fi;
            auto c=g[u].begin()->se,d=g[u].rbegin()->se;
            link(x,y,{(c[0]*d[1]+c[1]*d[0])%MOD,c[1]*d[1]%MOD});
        }
        for(auto e:g[u]) g[e.fi].erase(u),upd(e.fi);
        g[u].clear();
    }
    printf("%lld\n",ans);
    return 0;
}