解题思路

直接求可行方案不是很方便，所以试着反过来。
$N$个节点的无向连通图总数 $=$ $N$个节点的无向图总数 $-N$个节点的无向非连通图总数。
以$dp[i]$表示 $i$ 个节点的无向连通图总数。

$i$ 个节点的无向图

由于其边总数至多有 $i$ $\times$ $(i - 1)/2$条。
每条边有存在与不存在两种情况。
所以 $i$个节点的无向图总数为$2^{i \times (i - 1)/2}$。

$i$ 个节点的无向图非连通图

试枚举包含结点1的连通块大小为 $j$。
显然这个连通块有 $\binom{i - 1}{j - 1}$ 种选法。
那么这个连通块可能的情况总数就有$dp[j] \times \binom{i - 1}{j - 1}$ 种。
除该连通块外剩余 $i - j$个节点，共有$2^{(i - j) \times (i - j - 1)/2}$种组合。
得$i$ 个节点的无向图非连通图总数为$ \sum_{j=1}^{i - 1} dp[j] \times \binom{i - 1}{j - 1} \times 2^{(i - j) \times (i - j - 1)/2}$。

最后根据上述推导得递推式：
$dp[1] = 1$。
$dp[i] = 2^{i \times (i - 1)/2} - \sum_{j=1}^{i - 1} dp[j] \times \binom{i - 1}{j - 1} \times 2^{(i - j) \times (i - j - 1)/2} $。

标程

#include<iostream>
#include<map>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

struct bign
{
    int d[2010];
    int len;
    bign(){ memset(d,0,sizeof(d)); len=0;}
};

const int maxn=55;
int n;
bign C[maxn][maxn];
bign dp[maxn];

bign add(bign a,bign b)
{
    bign c;
    int carry=0;
    for(int i=0;i<a.len||i<b.len;i++)
    {
        int num=a.d[i]+b.d[i]+carry;
        c.d[c.len++]=num%10;
        carry=num/10;
    }
    if(carry!=0) c.d[c.len++]=carry;
    return c;
}

bign mul(bign a,bign b)
{
	bign c; int carry=0;
	if((a.len==1&&a.d[0]==0)||(b.len==1&&b.d[0]==0)){ c.len=1; return c;}
	for(int i=0;i<a.len;++i)
	for(int j=0;j<b.len;++j)
	{
		c.d[i+j]+=a.d[i]*b.d[j];
		if(c.d[i+j]!=0) carry=i+j;
	}
	
	for(int i=0;i<=carry+7;++i)
	{
		c.d[i+1]+=c.d[i]/10;
		c.d[i]%=10;
		if(c.d[i]!=0) c.len=i+1;
	}
	return c;
}

bign qpow(int k)
{
	bign a,c;
	c.len=1; c.d[0]=1;
	a.len=1; a.d[0]=2;
	
	while(k>0)
	{
		if(k&1) c=mul(c,a);
		a=mul(a,a);
		k>>=1;
	}
	return c;
}

bign sub(bign a,bign b)
{
	bign c;
	
	for(int i=0;i<a.len||i<b.len;++i)
	{
		if(a.d[i]<b.d[i]){ a.d[i+1]--; a.d[i]+=10;}
		c.d[c.len++]=a.d[i]-b.d[i];
	}
	while(c.len-1>=1&&c.d[c.len-1]==0) c.len--;
	return c;
}

void print(bign c)
{
	for(int i=c.len-1;i>=0;--i)
	printf("%d",c.d[i]);
}

int main()
{
    for(int i=1;i<=50;++i)
    {
    	C[i][0].len=1; C[i][0].d[0]=1;
    	C[i][i].len=1; C[i][i].d[0]=1;
    	for(int j=1;j<i;++j)
    	C[i][j]=add(C[i-1][j],C[i-1][j-1]);
	}
    
	dp[1].len=1; dp[1].d[0]=1;
	for(int i=2;i<=50;++i)
	{
		bign c;
		dp[i]=qpow(i*(i-1)>>1);
		for(int j=1;j<i;++j)
		c=add( c, mul( dp[j], mul( C[i-1][j-1], qpow((i-j)*(i-j-1)>>1) ) ) );
		dp[i]=sub(dp[i],c);
	}
	
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)break;
		print(dp[n]);printf("\n");
	}
	return 0;
}