问题：求含有n个点的连通图的个数。
解：
考虑DP，$f(n)$表示n个点，每个点都和点1相连，且n个点互相连通的图的个数。
（蓝字非常重要，这个条件有效地避免了重复计算）
$g(n)$表示n个点，每个点都和点1相连，且不是n个点互相连通的图的个数。
$S(n)$表示n个点的图的个数。
显然，有：$f(n) = S(n)-g(n)$
$S(n) = 2^{n(n-1)/2}$
而且有（关键）：$g(n) = \sum_{i=1}^{n-1}{C_{n-1}^{i-1} * f(i) * S(n-i)}$
从除了1之外的n-1个点中选出i-1个点，让这i个点互相连通，而剩下的n-i个点和这i个点没有边相连，互相之间随意连接。
当然，博主并不想写高精度
#include <iostream>
#include <cstring>
#include <algorithm> #define LL long long
#define N 61 using namespace std; LL f[N],g[N];
LL C[N][N];
const int n=; LL S(int x){
if(x==) return ;
return (1LL<<( (x*(x-)) /));
} int main(){
f[]=; g[]=;
C[][]=;
for(int i=;i<=n;i++){
C[i][]=;
for(int j=;j<=i;j++)
C[i][j]=C[i-][j-]+C[i-][j];
}
for(int i=;i<=n;i++){
g[i]=;
for(int j=;j<i;j++)
g[i] = g[i] + (C[i-][j-]*f[j]*S(i-j));
f[i]=S(i)-g[i];
}
int x;
while(cin>>x,x) cout<<f[x]<<endl;
return ;
}
接下来是多校联盟中有关于本题的拓展：
问题：求左侧n个点，右侧m个点的联通二分图个数
解：参照上面的解法。
$f(i,j)$表示左面i个点右面j个点，每个点都和左面的点1相连，且n个点互相连通的图的个数。
$g(i,j)$表示左面i个点右面j个点，每个点都和左面的点1相连，且n个点不是互相连通的图的个数。
$S(i,j)$定义类比上面。
和上面一样的，有：
$f(n,m)=S(n,m)-g(n,m)$
$S(n,m)=2^{nm}$
$g(n,m)=\sum_{r=1}^{n-1}{ \sum_{s=1}^{m-1}{ C_{n-1}^{r-1}*C_{m}^{s}*f(r,s)*S(n-r,m-s) } }$