AOJ 799.热身之回家养猪

Time Limit: 1000 ms Case Time Limit: 1000 ms Memory Limit: 64 MB
Total Submission: 203 Submission Accepted: 14

Description

快毕业了，同学们开始为自己的未来做打算。某人打算回家养猪。由于养猪还得去卖，所以交通是个问题，现在有n个村庄，村庄的编号是1到n，有m条路。若想使得所有的村庄连通，至少还需要修多少条路？

Input

题目包括多组输入
第一行，n,m 1<=n<=1000, 0<=m<=n^2
接下来m行，每行两个数 a,b ，用空格分隔，表示村庄a到村庄b已经有一条道路

Output

一行，一个数ans，表示至少还需要修的路的数量

Sample Input

Original Transformed
3 1
1 2
Sample Output

Original Transformed
1
Hint

需要修一条1到3的边或者2到3的边

http://icpc.ahu.edu.cn/OJ/ContestProblem.aspx?cid=151&id=799

可采用并查集求解，然而当时对并查集并不怎么熟练

采用了较为暴力的写法

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <string>
 6 #include <iostream>
 7 #include <vector>
 8 #include <list>
 9 #include <stack>
10 #include <queue>
11 using namespace std;
12  
13 #define REP(n) for(int o=0;o<n;o++)
14  
15 const int maxn = 1005;
16 int edge[maxn][maxn];
17  
18 inline void road(int a,int b) {
19     edge[a][++edge[a][0]] = b;
20     edge[b][++edge[b][0]] = a;
21     //printf("     %d %d
",a,b);
22 }
23  
24 bool Do() {
25     int n,m;
26     if(scanf("%d%d",&n,&m) == EOF)
27         return false;
28     for(int i = 1;i <= n;i++)
29         edge[i][0] = 0;
30     REP(m) {
31         int a,b;
32         scanf("%d%d",&a,&b);
33         road(a,b);
34     }
35     bool can[maxn] = {0};
36      
37     int cnt = 0;
38  
39     queue<int> Q;
40     Q.push(1);
41  
42     while(!Q.empty()) {
43         int top = Q.front();
44         Q.pop();
45         if(can[top])
46             continue;
47         can[top] = 1;
48         REP(edge[top][0])
49             Q.push(edge[top][o+1]);
50     }
51     /*
52     printf("===
");
53     REP(n)
54         printf("can[%d]=%d
",o + 1,can[o + 1]);
55         */
56     while(1) {
57         bool ok = true;
58         REP(n) {
59             if(!can[o + 1]) {
60                 road(1,o + 1);
61                 cnt++;
62                 Q.push(o + 1);
63                 while(!Q.empty()) {
64                     int top = Q.front();
65                     Q.pop();
66                     if(can[top])
67                         continue;
68                     can[top] = 1;
69                     REP(edge[top][0]) {
70                         Q.push(edge[top][o+1]);
71                     }
72                 }
73                 ok = false;
74                 break;
75             }
76         }
77         if(ok)
78             break;
79     }
80     printf("%d
",cnt);
81     return true;
82 }
83  
84 int main() {
85     while(Do());
86     return 0;
87 }