设f(n)为所求答案

g(n)为n个顶点的非联通图

则f(n) + g(n) = h(n) = 2^(n * (n - 1) / 2)

其中h(n)是n个顶点的联图的个数

这样计算

先考虑1所在的连通分量包含哪些顶点

假设该连通分量有k个顶点

就有C(n - 1, k - 1)种集合

确定点集后，所在的连通分量有f(k)种情况。其他连通分量有 h(n - k)种情况

因此有递推公式。g(n) = sum{ C(n - 1, k - 1) * f(k) * h(n - k)} 其中k = 1,2...n-1

注意每次计算出g(n)后立刻算出f(n)

import java.math.BigInteger;

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		BigInteger two[] = new BigInteger [55];

		two[0] = BigInteger.ONE;

		for(int i = 1; i <= 50; i++)

			two[i] = two[i - 1].multiply(BigInteger.valueOf(2));

		BigInteger h[] = new BigInteger [55];

		for(int i = 1; i <= 50; i++){

			int a = i;

			int b = i - 1;

			if(a % 2 == 0) a/= 2;

			else b /= 2;

			h[i] = BigInteger.ONE;

			for(int j = 0; j < a; j++) {

				h[i] = h[i].multiply(two[b]);

			}

		}

		BigInteger C[][] = new BigInteger[55][55];

		C[0][0] = BigInteger.ONE;

		for(int i = 0; i <= 50; i++){

			C[i][0] = C[i][i] = BigInteger.ONE;

			for(int j = 1; j < i; j++){

				C[i][j] = C[i - 1][j].add(C[i - 1][j - 1]);

			}

		}

		BigInteger f[] = new BigInteger[55];

		BigInteger g[] = new BigInteger[55];

		f[1] = BigInteger.ONE;

		for(int i = 2; i <= 50; i++) {

			g[i] = BigInteger.ZERO;

			for(int j = 1; j < i; j++) {

				g[i] = g[i].add(C[i - 1][j - 1].multiply(f[j]).multiply(h[i - j]));

			}

			f[i] = h[i].subtract(g[i]);

		}

		int n;

		Scanner cin = new Scanner(System.in);

		while(cin.hasNext()){

			n = cin.nextInt();

			if(n == 0) break;

			System.out.println(f[n]);

		}

	}

}