自动搬运

查看原文

来自洛谷，原作者为

	Karry5307 兄弟会背叛你，女人会离开你，金钱会诱惑你，生活会刁难你，只有数学不会，不会就是不会，怎么学都不会

搬运于2025-08-24 22:24:01，当前版本为作者最后更新于2021-02-03 10:27:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

给定一个 $n$ 个点 $m$ 条边的图，保证这个图删掉一条边之后是边仙人掌，求该图生成树个数。

$\texttt{Data Range:}1\leq n,m\leq 5\times 10^5$

题解

广义串并联图。

注意到原图是广义串并联图，所以可以考虑对每条边进行 DP，然后在收缩的时候进行转移。

一个思路是设 $f_e$ 表示 $e$ 这条边在生成树上的方案，$g_e$ 表示这条边不在生成树上的方案，那么对于收缩的三种操作有：

• 删 $1$ 度点：直接将 $f_e$ 乘进答案即可。

• 缩 $2$ 度点：这两条边不可能同时不存在于生成树上，同时缩出来的边只有当两条边都存在时才存在，于是有如下转移：

$$\begin{cases}f_e=f_{e_1}f_{e_2}\\g_e=f_{e_1}g_{e_2}+f_{e_2}g_{e_1}\end{cases} $$

• 叠合重边：这两条边不可能同时存在于生成树上，同时缩出来的边只有当两条边都不存在时才不存在，于是有如下转移：

$$\begin{cases}f_e=f_{e_1}g_{e_2}+f_{e_2}g_{e_1}\\g_e=g_{e_1}g_{e_2}\end{cases} $$

然后拓扑排序构造出整个收缩序列即可，删边的话可以使用哈希表或者是 map，实测 map 比各种哈希表优秀，实现上有亿点细节要注意。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=5e5+51,MOD=998244353;
queue<ll>q;
ll n,m,u,v,totd,top,x,y,r,res=1;
ll f[MAXN],g[MAXN],deg[MAXN];
map<ll,ll>mp[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
int main()
{
    n=read(),m=read(),g[0]=1;
    for(register int i=1;i<=m;i++)
    {
    	u=read(),v=read();
		!mp[u][v]?g[mp[u][v]=mp[v][u]=++totd]=1,deg[u]++,deg[v]++:1;
		f[mp[u][v]]++;
	}
	for(register int i=1;i<=n;i++)
	{
		deg[i]<=2?q.push(i):(void)1;
	}
	while(!q.empty())
	{
		top=q.front(),q.pop();
		if(!deg[top])
		{
			continue;
		}
		if(deg[top]==1)
		{
			tie(u,x)=*mp[top].begin(),deg[top]=0,res=(li)res*f[x]%MOD;
			mp[top].clear(),mp[u].erase(top),--deg[u]<=2?q.push(u):(void)1;
		}
		if(deg[top]==2)
		{
			tie(u,x)=*mp[top].begin(),tie(v,y)=*next(mp[top].begin()),r=mp[u][v];
			mp[top].clear(),mp[u].erase(top),mp[v].erase(top),deg[top]=0;
			g[x]=((li)g[x]*f[y]+(li)f[x]*g[y])%MOD,f[x]=(li)f[x]*f[y]%MOD;
			f[x]=((li)f[x]*g[r]+(li)g[x]*f[r])%MOD,g[x]=(li)g[x]*g[r]%MOD;
			mp[u][v]=mp[v][u]=x;
			r?--deg[u]<=2?q.push(u):(void)1,--deg[v]<=2?q.push(v):(void)1:(void)1;
		}
	}
	printf("%d\n",res);
}