解题报告

wwwlehu6.vip乐虎官网,畅通project

Time Limit:
4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 37204    Accepted Submission(s): 19715

Problem Description

某省考察城市和集镇交通景况。获得现存城市和商场征程计算表。表中列出了每条道路一贯对接的市场。

省府“畅通project”的靶子是使全省不论什么五个市场间都能够达成交通(但不自然有一向的征途不断。仅仅要相互直接通过道路可达就足以)。问最少还须要建设多少条道路? 

 

Input

測试输入包罗若干測试用例。每三个測试用例的第三行提交四个正整数,各自是城市和市集数据N
( < 1000)和道路数目M。随后的M行相应M条道路,每行给出1对正整数。各自是该条道路向来对接的八个村镇的数码。为简便起见,城市和市镇从一到N编号。 
在意:五个城市里面能够有多条道路相通,也正是说
3 3
1 2
1 2
2 1
如此那般的输入也是法定的
当N为0时,输入完结。该用例不被处理。

 

 

Output

对每1个測试用例,在1行里输出最少还要求建设的征途数据。 

 

Sample Input

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

 

Sample Output

1
0
2
998

HintHint 
Huge input, scanf is recommended.

题解:并查集模板题。

參考代码:

#include<stdio.h>
int father[1005];
int find(int n)
{
    return father[n]==n?n:father[n]=find(father[n]);
}
void merge(int x,int y)
{
    int fx,fy;
    fx=find(x);
    fy=find(y);
    if(fx!=fy)
        father[fx]=fy;
}
int main()
{
    int n,m,a,b,sum;
    while(~scanf("%d",&n))
    {
        if(n==0)break;
        scanf("%d",&m);
        sum=0;
        for(int i=1;i<=1001;i++)
            father[i]=i;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            merge(a,b);
        }
        for(int i=1;i<=n;i++)
        {
            if(father[i]==i)
                sum++;
        }
        printf("%d\n",sum-1);
    }
    return 0;
}
You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图