n个点m条边构成的简单⽆相连通图个数
n个点m条边构成的简单⽆相连通图个数
今天思考这个问题，上⽹查询发现资料甚少（BJ没到。。。）
所以解决这个了问题，就来写⼀篇blog
先讲下代码都是⽤数学⽅法检验后好好拍过的，正确性不必担⼼为了⽅便测⼤数据加了mod
对于这个问题我们先不思考正解
先给个暴⼒
做法是枚举所有的边是否选，之后判断连通性
可以跑到点数<=8的图
//没好好打将就看吧。。。
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=100100,mod=int(1e9)+7;
int n,m,tot,ans;
int U[N],V[N],fa[N],d[N];
inline int find(int x)
{
while(fa[x]^x)x=fa[x];
return x;
}
inline void merger(int x,int y)
{
if(d[x]==d[y])
{
fa[x]=y;
d[y]++;
return ;
}
if(d[x]>d[y])swap(x,y);
fa[x]=y;
}
inline bool check()
{
int tmp=find(1);//cout<<tmp<<endl;
for(int i=2;i<=n;++i)if(find(i)^tmp)return 0;
return 1;
}
void dfs(int step,int now)
{
if(now==m)
{
if(check())ans++;ans%=mod;
return ;
}
if(step>tot)return ;
dfs(step+1,now);
int pre[4];
pre[0]=find(U[step]);pre[1]=find(V[step]);
pre[2]=d[pre[0]];pre[3]=d[pre[1]];//cout<<pre[0]<<" "<<pre[1]<<endl;  if(pre[0]^pre[1])
{
merger(pre[0],pre[1]);
}
dfs(step+1,now+1);
fa[pre[0]]=pre[0];fa[pre[1]]=pre[1];
d[pre[0]]=pre[2];d[pre[1]]=pre[3];
}
int solve()
{
n=read();m=read();
int i,j;
for(i=1;i<=n;++i)fa[i]=i;
ans=0;
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
{
U[++tot]=i;V[tot]=j;
}//cout<<tot<<endl;
if(n==1)
{
puts("0");return 0;
}
dfs(1,0);
cout<<ans<<endl;return 0;
}
int main()
{//freopen("data.in","r",stdin);freopen("pai.out","w",stdout);
solve();/*
for(i=2;i<=10;++i)
{cout<<i<<" ";
cout<<solve(i)<<endl;
}*/
return 0;
}
/*
5 4
*/
之后我们来说正解
我最开始想的是在⼀个已经连通的n-1个点的图中插⼊点，再加上n-1个不连通加上该点连通的⽅案数然后发现不是很好做，果断弃掉
之后可以怎么搞呢
考虑逆向思维
⽤所有⽅案减去不合法⽅案
具体是什么样⼦呢？
令E(i)表⽰点数为i的完全图边数
f(i,j)表⽰i个点j条边的简单⽆相连通图个数
我们枚举1号点所在联通块的⼤⼩为a及其内部的边数为b
所以就有如下的式⼦
然后代码是酱紫的
//经过测试发现组合数前⾯那句m>n很重要啊
//虽然我并不觉得它会越界捂脸熊
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<map>
#include<set>
#include<set>
using namespace std;
typedef long long ll;
inline int read()
cstring转为int{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}
const int N=110,M=100100,mod=int(1e9)+7;
int f[N][N],e[N];
int fac[M],inv[M];
void initial()
{
register int i;
for(i=1;i<N;++i)e[i]=1ll*i*(i-1)>>1;
fac[0]=1;for(i=1;i<M;++i)fac[i]=1ll*fac[i-1]*i%mod;
inv[1]=1;for(i=2;i<M;++i)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
inv[0]=1;for(i=1;i<M;++i)inv[i]=1ll*inv[i]*inv[i-1]%mod;
}
inline int C(int n,int m)
{if(m>n)return 0;return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main()
{//freopen("data.in","r",stdin);freopen("dui.out","w",stdout);
int n=read(),m=read();
register int i,j,a,b;
initial();
f[1][0]=1;
for(i=2;i<=n;++i)
{
for(j=i-1;j<=min(e[i],m);++j)
{
f[i][j]=C(e[i],j);
for(a=1;a<=i-1;++a)
{
for(b=a-1;b<=min(e[a],j);++b)
{
f[i][j]=(1ll*f[i][j]-1ll*f[a][b]*C(e[i-a],j-b)%mod*C(i-1,a-1)%mod+mod)%mod;    }
}
}
}
cout<<f[n][m]<<endl;
}
这是今天在cnblog和⼀个盆友讨论的问题

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。