Build the Railway ACM

dianlongliu

一个下午终于把前天ACM没有做出来的提搞定拉.
大家看看有没有更优的解拉..
题意:基本就是求缺少的铁路数.

There are n cities in A country. The country has already built part of a railway. The both sides of the railway are connecting different cities, and a two-way street. Some cities may not connect (Together means with direct access or indirectly up). In order to cause the transportation to be unimpeded, this country decided to construct the railway, so that any two cities are connected. But this country does not want to spend too much money, it would like to construct as far as possible few railways.

Input

Each group of test data is composed of 2 parts. The first line is two positive integer n, m (n<=100, m<=1000). n expressed that there are n cities, m expressed there have already built m railways. n cities that were marked as 1, 2, …, n, Then there are m lines. Each group has two positive integers a, b (1<=a, b<=n) , expressed that a, b, has a railway. When n=m=0 finished.

Output

Outputs integer min regarding each group of test data, said that the construction of the railway at least.

Sample Input

2 1
1 2
3 1
1 2
0 0

Sample Output

0
1




#include <stdio.h>
int a[150][150]={0};
       
void games(int l,int m)
        {
                int start=l;
                int end=m;
                int i,N=1,k,j;
                for(i=0;i<N;i++)
                {
                        for(j=start;j<end;j++)
                                for(k=0;k<end;k++)
                                {
                                        if(j>=k&&a[0][k]==0&&a[j][k]==1)
                                                N++;
                               
                                        if(a[j][k]==1)
                                                a[0][k]=1;
                                }
                }
        }


void main(void )
{
        void games(int l,int n);
        int count=0;
        int n,m,j,k,x,y,i;
       

        scanf("%d %d",&n,&m);
        for(i=0;i<m;i++)
        {
                scanf("%d %d",&x,&y);
                a[x-1][y-1]=a[y-1][x-1]=1;
        }
       
        int l=0;
        games(l,n);
        for(i=1;i<=n;i++)
        {
                if(a[0]==0)
                {
                        a[0]=1;
                        l=i-1;
                        count++;
                        games(l,n);
                }
        }
       
        printf("%d\n",count);

}

调试成功.

[ 本帖最后由 dianlongliu 于 2008-4-30 13:56 编辑 ]