2013
11-10

# Connected Graph

An undirected graph is a set V of vertices and a set of E∈{V*V} edges.An undirected graph is connected if and only if for every pair (u,v) of vertices,u is reachable from v.

You are to write a program that tries to calculate the number of different connected undirected graph with n vertices.

For example,there are 4 different connected undirected graphs with 3 vertices.

The input contains several test cases. Each test case contains an integer n, denoting the number of vertices. You may assume that 1<=n<=50. The last test case is followed by one zero.

For each test case output the answer on a single line.

1
2
3
4
0


1
1
4
38


import java.util.*;
import java.math.*;

public class Main
{
BigInteger[] ans = new BigInteger[52];
public Main()
{
DP();
solve();
}
//姹�����
BigInteger combinationNum(int n, int m)
{
BigInteger ret = new BigInteger("1");
int i;
for (i = 0; i < m; ++i)
{
ret = ret.multiply(new BigInteger(n - i + ""));
ret = ret.divide(new BigInteger(i + 1 + ""));
}
return ret;
}

void DP()
{
ans[1] = new BigInteger("1");
ans[2] = new BigInteger("1");
int i, j;
BigInteger tmp = new BigInteger("0");
BigInteger com = new BigInteger("0");
for (i = 3; i <= 50; ++i)
{
ans[i] = new BigInteger("0");
for (j = 1; j < i; ++j)
{
com = combinationNum(i - 2, j - 1);
tmp = ans[j].multiply(ans[i - j]);
tmp = tmp.multiply(com);
tmp = tmp.multiply(new BigInteger(((long)1 << j) - 1 + ""));
}
}
//for (i = 1; i <= 50; ++i)
//   System.out.println(i + ": " + ans[i]);
}
void solve()
{
int n;
Scanner cin = new Scanner(System.in);
while (true)
{
n = cin.nextInt();
if (n == 0)
return;
System.out.println(ans[n]);
}
}

public static void main(String args[])
{
new Main();
}
}

1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。