Forest Program（仙人掌）

original link - http://acm.hdu.edu.cn/showproblem.php?pid=6736

题意：

仙人掌定义：无重边、自环，每条边被最多一个简单环包含。

有多少种删除边的方案使得剩余图为森林。

解析：

先将所有环的环长$len$， 2 l e n − 1 2^{len}-1 2len−1乘入答案，最后剩余的边可以选择删或者不删，就是 2 k 2^k 2k。

这个这么处理呢？我们可以一遍搜索解决一个连通图，用类似深度的概念来标记每个点。如果搜到一个深度较小的点，说明当前为一个环，那么环长为$\delta len+1$。

代码：

/**  Author : Jk_Chen*    Date : 2019-09-28-12.10.15*/
#include
using namespace std;
#define LL long long
#define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pill pair
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<
const LL mod=998244353;
const int maxn=5e5+9;
const int inf=0x3f3f3f3f;
LL rd(){ LL ans=0; char last=' ',ch=getchar();while(!(ch>='0' && ch<='9'))last=ch,ch=getchar();while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();if(last=='-')ans=-ans; return ans;
}
#define rd rd()
/*_________________________________________________________begin*/#define rep_e(i,p,u) for(int i=head[p],u=to[i];i;i=nex[i],u=to[i])
int head[maxn],to[maxn<<1],nex[maxn<<1],now;
void add(int a,int b){nex[++now]=head[a];head[a]=now;to[now]=b;
}
void init_edge(){memset(head,0,sizeof head);now=0;
}
/*_________________________________________________________edge*/bool vis[maxn];
LL P2[maxn];LL mul;
int edg;
int dfn[maxn];
void dfs(int p){vis[p]=1;rep_e(i,p,u){if(dfn[u]&&dfn[u]==dfn[p]-1)continue;if(!dfn[u]){dfn[u]=dfn[p]+1;dfs(u);continue;}if(dfn[u]>dfn[p])continue;int len=dfn[p]-dfn[u]+1;mul=mul*(P2[len]-1)%mod;edg-=len;}
}int main(){P2[0]=1;rep(i,1,maxn-1)P2[i]=(P2[i-1]<<1)%mod;int n,m;while(cin>>n>>m){init_edge();mmm(vis,0);mmm(dfn,0);edg=m;if(m==0){printf("1\n");continue;}rep(i,1,m){int a=rd,b=rd;add(a,b),add(b,a);}mul=1;rep(i,1,n){if(!vis[i])dfn[i]=1,dfs(i);}mul=mul*P2[edg]%mod;printf("%lld\n",(mul+mod)%mod);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！