题目意思很明了，计算一个n个顶点的无向连通图的数量
可以这样思考:
n个顶点的无相连通图构成方法为在n-1个节点中分离出一个大小为i的联通分量加上第n个节点与剩余的n-1-i个点构成的联通分量（可能n-1-i个点并不联通，但是可以通过第n个点联通），所以初步的式子是这样：
dp[i]=sum{dp[j]*(1 shl j-1)*dp[i-j]*c[j-1][i]}
但是这个式子有点问题，会产生重复，如图所示
1）
2）
1）和2）其实是同一种状态，但是按 算选出（1，2）是一种，选出（3，4）是一种，所以产生了重复。
那么该怎么修改呢，其实只要固定一个点，假设是1，再从n-1个点中选出i-1个点去跟1构成连通图即Ci-1n-1，那样就可以避免重复了；
所以式子修正为
dp[i]=sum{dp[j]*(1 shl j-1)*dp[i-j]*c[j-2][i-1]}
不知道网上很多人为什么要从反面考虑，即算出n无向图的个数2^C[n][2]然后再减去不连通的诱导子图数目，感觉是多此一举~
1 import java.io.*;
2 import java.math.*;
3 public class Main {
4
5 /**
6 * @param args
7 */
8 public static void main(String[] args) throws IOException{
9 BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
10 BigInteger dp[]=new BigInteger[60];
11 BigInteger c[][]=new BigInteger[51][51];
12 c[0][0]=BigInteger.ONE;
13 for(int i=1;i<=50;i++)
14 c[i][0]=c[i][i]=BigInteger.ONE;
15 for(int i=2;i<=50;i++)
16 for(int j=1;j<i;j++)
17 c[i][j]=c[i-1][j].add(c[i-1][j-1]);
18 dp[1]=BigInteger.ONE;
19 dp[0]=BigInteger.ONE;
20 for(int i=2;i<=50;i++)
21 {
22 dp[i]=BigInteger.ZERO;
23 for(int j=1;j<i;j++)
24 dp[i]=dp[i].add(dp[j].multiply((BigInteger.ONE.shiftLeft(j)).add(BigInteger.ONE.negate())).multiply(dp[i-j]).multiply(c[i-2][j-1]));
25 }
26 int num=0;
27 while(true)
28 {
29 num=Integer.parseInt(in.readLine());
30 if(num==0) break;
31 System.out.println(dp[num]);
32 }
33
34 }
35
36 }
37