poj 1737 Connected Graph

题目链接：http://poj.org/problem?id=1737

方法一：考虑反面，即不连通的个数，则分类讨论种结点1连通的个数，其它点随便连，F(n)= 2^(C(n,2))-Sum(C(n-1,k)*F(k+1)* 2^(C(n-k-1,2)) | 0<=k<n);

方法二：我们将1作为2所在的连通子图与其它结点的割点，当然1和其它结点连通，枚举2所在的连通子图的结点数，则F(n)=Sum(F(k)*F(n-k)* C(n-2,k-1)*( 2^k-1) | 1<=k<n);

import java.math.BigInteger;
import java.util.Scanner;


public class Main
{
	public static BigInteger[]two=new BigInteger[52];
	public static BigInteger[]dp=new BigInteger[52];
	public static BigInteger[][]c=new BigInteger[52][52];
	public static void init()
	{
		int i,j;
		two[0]=BigInteger.ONE;
		for(i=1;i<=51;i++)
			two[i]=two[i-1].multiply(BigInteger.valueOf(2));
		for(i=0;i<51;i++)
			c[i][0]=two[0];
		for(i=0;i<51;i++)
			c[i][i]=two[0];
		for(i=1;i<50;i++)
			for(j=1;j<i;j++)
			{
				c[i][j]=c[i-1][j].add(c[i-1][j-1]);
				//System.out.println(i+" "+j+" "+c[i][j]);
			}
		dp[1]=dp[2]=BigInteger.ONE;
		for(i=3;i<=50;i++)
		{
			dp[i]=BigInteger.ZERO;
			for(j=1;j<i;j++)
				dp[i]=dp[i].add(dp[j].multiply(dp[i-j]).multiply(c[i-2][j-1]).multiply(two[j].subtract(two[0])));
		}
	}
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		int n;
		init();
		while(sc.hasNext())
		{
			
			n=sc.nextInt();
			if(n==0)
				break;
			System.out.println(dp[n]);
		}
	}
}