2 条题解
-
0
首先我们对图进行分类讨论。如果图不是仙人掌，那么直接输出 0 即可。如果图存在环，那么我们之后加的边肯定不会跨过这个环，所以我们把仙人掌拆分成无环的几个部分（把环给丢掉），形成了几棵独立的树。所以我们最终还是要在树上做。然后我们考虑加边变成环其实等价于找到几条互相没有交集的路径，然后路径的端点连边，就能构成仙人掌。所以问题转化成了在树上有多少选择若干条互相没有交集的仙人掌的方案数。我们可以考虑 DP。关于树上路径的覆盖选择问题可以这样设状态 f[u,0/1] 表示 u 及其子树，是否会有一条从 u 子树生长到祖先的路径。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=5e5+10; const LL mod=998244353ll; inline int qr() { int x=0, f=1;char c=getchar(); for(;!isdigit(c);c=getchar()){if(c=='-') f=-1;} for(; isdigit(c);c=getchar())x=x*10+c-48; return x*f; } vector<int>G1[N],G2[N]; int tsp,cnt,dfn[N],low[N],scc[N]; stack<int>stk; LL f[N][2],g[N],ans=1; bool flag=1,vis[N]; void tarjan(int x,int xfa) { dfn[x]=low[x]=++tsp; stk.push(x); int num=0; for(int y:G1[x]) if(y!=xfa) { if(!dfn[y]) { tarjan(y,x); low[x]=min(low[x],low[y]); } else low[x]=min(low[x],dfn[y]); if(dfn[x]>low[y]) { ++num; if(num>1) {flag=0; return;} } if(flag==0) return; } if(dfn[x]==low[x]) { cnt++; for(int z=-1;z!=x;) { z=stk.top(); stk.pop(); scc[z]=cnt; } } } void dfs(int x,int xfa) { int sc=G2[x].size()-(xfa!=0); vis[x]=1; f[x][0]=g[sc]; f[x][1]=(sc>0?g[sc-1]*sc%mod:0); for(int y:G2[x])if(y!=xfa) { dfs(y,x); f[x][0]=f[x][0]*f[y][1]%mod; f[x][1]=f[x][1]*f[y][1]%mod; } f[x][1]=(f[x][1]+f[x][0])%mod; } signed main() { int T=qr(); while(T--) { int n=qr(), m=qr(); //memset(G1,0,sizeof(G1));//用memset此题会超时 for(int i=1;i<=n;i++)G1[i].clear(),G2[i].clear(); for(int i=1;i<=m;i++) { int x=qr(), y=qr(); G1[x].push_back(y); G1[y].push_back(x); } tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); memset(scc,0,sizeof(scc)); flag=1;tarjan(1,0); if(!flag){puts("0"); continue;} //memset(G2,0,sizeof(G2));//用memset此题会超时 for(int x=1;x<=n;x++)for(int y:G1[x]) if(scc[x]!=scc[y]) G2[x].push_back(y); ans=1;memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); g[0]=g[1]=1;for(int i=2;i<=n;i++) g[i]=((i-1)*g[i-2]+g[i-1])%mod; for(int i=1;i<=n;i++)if(!vis[i]) dfs(i,0), ans=ans*f[i][0]%mod; printf("%lld\n",ans); } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:11:15
/* 首先我们对图进行分类讨论。如果图不是仙人掌，那么直接输出 0 即可。 如果图存在环，那么我们之后加的边肯定不会跨过这个环， 所以我们把仙人掌拆分成无环的几个部分（把环给丢掉），形成了几棵独立的树。 所以我们最终还是要在树上做。 然后我们考虑加边变成环其实等价于找到几条互相没有交集的路径， 然后路径的端点连边，就能构成仙人掌。所以问题转化成了在树上 有多少选择若干条互相没有交集的仙人掌的方案数。 我们可以考虑 DP。关于树上路径的覆盖选择问题可以这样设状态 f[u,0/1] 表示 u 及其子树，是否会有一条从 u 子树生长到祖先的路径。 */ #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=5e5+10; const LL mod=998244353ll; inline int qr() { int x=0, f=1;char c=getchar(); for(;!isdigit(c);c=getchar()){if(c=='-') f=-1;} for(; isdigit(c);c=getchar())x=x*10+c-48; return x*f; } vector<int>G1[N],G2[N]; int tsp,cnt,dfn[N],low[N],scc[N]; stack<int>stk; LL f[N][2],g[N],ans=1; bool flag=1,vis[N]; void tarjan(int x,int xfa) { dfn[x]=low[x]=++tsp; stk.push(x); int num=0; for(int y:G1[x]) if(y!=xfa) { if(!dfn[y]) { tarjan(y,x); low[x]=min(low[x],low[y]); } else low[x]=min(low[x],dfn[y]); if(dfn[x]>low[y]) { ++num; if(num>1) {flag=0; return;} } if(flag==0) return; } if(dfn[x]==low[x]) { cnt++; for(int z=-1;z!=x;) { z=stk.top(); stk.pop(); scc[z]=cnt; } } } void dfs(int x,int xfa) { int sc=G2[x].size()-(xfa!=0); vis[x]=1, f[x][0]=g[sc], f[x][1]=(sc>0?g[sc-1]*sc%mod:0); for(int y:G2[x])if(y!=xfa) { dfs(y,x); f[x][0]=f[x][0]*f[y][1]%mod; f[x][1]=f[x][1]*f[y][1]%mod; } f[x][1]=(f[x][1]+f[x][0])%mod; } signed main() { int T=qr(); while(T--) { int n=qr(), m=qr(); //memset(G1,0,sizeof(G1));//用memset此题会超时 for(int i=1;i<=n;i++)G1[i].clear(),G2[i].clear(); for(int i=1;i<=m;i++) { int x=qr(), y=qr(); G1[x].push_back(y); G1[y].push_back(x); } tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); memset(scc,0,sizeof(scc)); flag=1;tarjan(1,0); if(!flag){puts("0"); continue;} //memset(G2,0,sizeof(G2));//用memset此题会超时 for(int x=1;x<=n;x++)for(int y:G1[x]) if(scc[x]!=scc[y]) G2[x].push_back(y); ans=1;memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); g[0]=g[1]=1;for(int i=2;i<=n;i++) g[i]=((i-1)*g[i-2]+g[i-1])%mod; for(int i=1;i<=n;i++)if(!vis[i]) dfs(i,0), ans=ans*f[i][0]%mod; printf("%lld\n",ans); } return 0; }
- 1
