題目意思很明了，計算一個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