Massive Algorithms: POJ 1737

http://poj.org/problem?id=1737

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.

Input

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.

Output

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

Sample Input

Sample Output

https://oi.men.ci/poj-1737/

给定

N

（

N \leq 50

）个点，在平面上固定其位置，求这些点最多能组成多少个不同的无向连通图。

统计连通图的方案数是困难的，但我们可以轻易地计算出用 N 个点组成任意图的方案数：因为 N 个点的无向图最多有

\frac{N(N - 1)}{2}

条边，考虑每条边选或不选，则共有

2 ^ {\frac{N(N - 1)}{2}}

种不同的图。

求出任意图的方案数后，只要再求出非连通图的方案数，就可以得到答案。考虑

N

个点组成的非连通图中的点

v

，它一定处于一个由

K

（

1 \leq K \leq N - 1

）个点组成的连通分量中，点

v

确定后，组成这个连通分量还需要

K - 1

个点，总方案数为

\binom{N - 1}{K - 1}

；每个连通分量都是一个连通图，可以递归来求；考虑完一个连通分量，图的剩余部分（与该连通分量隔离的

N - K

个点）是一个任意图，也可以递归来求。

设

n

个点组成连通图的方案数为

f(n)

、组成非连通图的方案数为

g(n)

、组成任意图的方案数为

h(n)

，则递归计算

f(n)

的公式为：

需要使用高精度。

http://www.voidcn.com/article/p-txqbeblo-bkm.html

    public static final int N = 55;
    public static void main(String[] args) throws Exception
    {
        BigInteger []h = new BigInteger[N];
        BigInteger []f = new BigInteger[N];
        BigInteger []g = new BigInteger[N];
        BigInteger p2[] = new BigInteger[N*N];
        BigInteger [][]C = new BigInteger[N][N];
        for (int i=0;i<N;i++)
        {
            for (int j=0;j<=i;j++)
            {
                if (i==j || j==0) C[i][j] = valueOf(1);
                else C[i][j] = C[i-1][j-1].add(C[i-1][j]);
            }
        }
        p2[0] = ONE;
        for (int i=1;i<N*N;i++)
            p2[i] = p2[i-1].multiply(valueOf(2));
        for (int i=0;i<N;i++)
            h[i] = p2[i*(i-1)/2];
        f[1] = BigInteger.valueOf(1);
        g[1] = BigInteger.valueOf(0);
        for (int n=2;n<N;n++)
        {
            g[n] = BigInteger.ZERO;
            for (int k = 1;k < n; k++)
            {
                BigInteger t = C[n-1][k-1].multiply(f[k]);
                t = t.multiply(h[n-k]);
                g[n] = g[n].add(t);
                f[n] = h[n].subtract(g[n]);
            }
        }
        Scanner in = new Scanner(System.in);
        while (in.hasNext())
        {
            int n = in.nextInt();
            if (n == 0) break;
            System.out.println(f[n]);
        }
    }

http://www.voidcn.com/article/p-zvbflxxn-uv.html

将总的方案数减掉所有不连通的方案。
总的方案数是2^(C(n,2))，不连通的方案数可以如下考虑：
当和点1连通的点数共有k个时，方案数为C(n-1,k) * F(k+1)，其他n-k-1各点间任意连边即可，方案数为2^(C(n-k-1,2))，所以这样的方案数共有C(n-1,k)* F(k+1)* 2^(C(n-k-1,2))种。
因此可以得到递推公式：
F(n)= 2^(C(n,2))-Sum(C(n-1,k)* F(k+1)* 2^(C(n-k-1,2)) | 0<=k < n)

https://blog.csdn.net/PoPoQQQ/article/details/43525019

令f[i]表示i个点能组成多少种无向图

首先易知我们能生成2^(i*(i-1)/2)种图但是一些是不合法的我们要将不合法的干掉

枚举1号节点与多少个点连通

设1号节点所在联通块大小为j(1<=j<=i-1)

那么与1相连的其它点有C(i-1,j-1)中选法，1号节点所在联通块有f[j]种连法，不与1号节点相连的点有2^((i-j)*(i-j-1)/2)种连法

故得到递推式f[i]=2^(i*(i-1)/2)-Σ[1<=j<=i-1]C(i-1,j-1)*f[j]*2^((i-j)*(i-j-1)/2)

w = open("out.out", "w")

f = [0] * 60

C = [[0] * 60 for i in range(60)]

for i in range(0,51):

C[i][0] = 1

for j in range(1,i+1):

C[i][j] = C[i-1][j] + C[i-1][j-1]

for i in range(1,51):

f[i] = 2**(i*(i-1)//2)

for j in range(1,i):

f[i] -= C[i-1][j-1] * (2**((i-j)*(i-j-1)/2)) * f[j]

w.write("\"%d\",\n" %f[i] )

POJ 1737 - Connected Graph

Labels

Popular Posts