（本篇要點）dfs找環并計算圖中環的長度，
Forest Program
題目傳送門：
Forest Program
題目大意：
有n個點和m條無向邊，要刪去一些邊使得剩下部分都為樹（就是沒有環），問有多少刪的方法，
思路：
如果n條邊剛好構成一個環，那么這些邊中就必須至少刪去一條邊，那么對于答案的貢獻就是 res = res * ( 2 ^ n - 1 )，
如果n條邊不夠成環，那么怎么刪都可以，那么對于答案的貢獻就為 res = res * 2^n ，
所以關鍵就是dfs，找到每個環，并計算每個環的長度，所有邊減去環中的邊，剩下的邊自然就是不在環中的邊，可以隨意洗掉，
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3e5+10,M=5e5+10;
const LL mod=998244353;
int head[N],cent=0;
struct Tree
{
int v,next;
}tr[M*2];
LL fac[M];
void add(int u,int v)
{
tr[cent].v=v;
tr[cent].next=head[u];
head[u]=cent++;
}
int dep[N],vis[N],n,m;
LL ans=1;
void dfs(int u,int fa)
{
vis[u]=1;
for(int i=head[u];~i;i=tr[i].next)
{
int to=tr[i].v;
if(to==fa) continue;
if(!vis[to])
{
dep[to]=dep[u]+1;
dfs(to,u);
continue;
}
if(dep[to]>dep[u]) continue;
int len=dep[u]-dep[to]+1;
ans=ans*(fac[len]-1)%mod;
m=m-len;
}
}
int main()
{
fac[0]=1;
for(int i=1;i<=M;i++)
fac[i]=fac[i-1]*2%mod;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<=n;i++)
{
head[i]=-1;
dep[i]=0;
vis[i]=0;
}
cent=0,ans=1;
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
dep[i]=1;
dfs(i,0);
}
}
ans=ans*fac[m]%mod;
printf("%lld\n",ans);
}
//system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/226964.html
標籤：其他