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;
}