# 畅通工程——浙大计算机研究生复试上机考试-2005年

2018/07/16 19:33

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

Problem Description

Input

3 3
1 2
1 2
2 1

Output

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
Hint
Hint
Huge input, scanf is recommended.

直接使用并查集即可，此题和我（找亲戚：https://www.cnblogs.com/chiweiming/p/9310599.html）那篇博客是类似的题目，

Java代码：
 1 import java.util.*;
2
3 public class 畅通工程 {
4
5     static int city[];
6
7     static int findFather(int jieDian) {    //找根节点
8         return jieDian==city[jieDian]?jieDian:findFather(city[city[jieDian]]);
9     }
10
11     public static void main(String[] args) {
13         ArrayList list=new ArrayList();    //动态数组
14         int result=0;
16         int count=0;
19
21             int save_N=N;
22             int M;
23             if(N!=0) {
24                 count++;
26             }
27             else {
28                 break;
29             }
30             city=new int[N+1];
31             for(int i=1;i<=N;i++) {    //首先指向本身
32                 city[i]=i;
33             }
34             for(int i=1;i<=M;i++) {    //建立城镇树
37                 int tou_One=findFather(city_One);
38                 int tou_Two=findFather(city_Two);
39                 if(tou_One!=tou_Two) {    //两个城镇不连通
40                     save_N--;    //2个城镇合并成1个
41                     if(tou_One<tou_Two) {
42                         city[tou_One]=tou_Two;
43                     }
44                     else {
45                         city[tou_Two]=tou_One;
46                     }
47                 }
48             }
49             result=save_N-1;    //sava_N个城镇用sava_N-1条路即可连接
51         }
52         for(int i=0;i<count;i++) {
53             System.out.println(list.get(i));
54         }
55     }
56
57 }
View Code

C代码：

 1 #include<stdio.h>
2 #include<stdlib.h>
3
4 int count=0;
5 int *arr;
6 int flag[1005];
7
8 int findFather(int jieDian){
9     return jieDian==arr[jieDian]?jieDian:findFather(arr[ arr[jieDian] ]);
10 }
11
12 int main(){
13
14     while(1){
15
16         int N;
17         scanf("%d",&N);
18         if(N==0){
19             break;
20         }
21         int sava_N=N;
22         count++;
23         int M;
24         scanf("%d",&M);
25         arr=(int *)malloc(sizeof(int)*(N+1));
26         for(int i=1;i<=N;i++){
27             arr[i]=i;    //指向本身
28         }
29         for(int i=1;i<=M;i++){
30             int relation_One;
31             int relation_Two;
32             scanf("%d%d",&relation_One,&relation_Two);
33             int fa_One=findFather(relation_One);
34             int fa_Two=findFather(relation_Two);
35             if(fa_One!=fa_Two) {
36                 sava_N--;
37                 if(fa_One<fa_Two){
38                     arr[fa_Two]=fa_One;
39                 }
40                 else{
41                     arr[fa_One]=fa_Two;
42                 }
43             }
44         }
45         flag[count]=sava_N-1;
46     }
47     for(int i=1;i<=count;i++){
48         printf("%d\n",flag[i]);
49     }
50
51     return 0;
52 }
View Code

19:32:41

2018-07-16

0
0 收藏

0 评论
0 收藏
0