AOJ 799.热身之回家养猪

154

题目


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    


3 1
1 2



Sample Output    


1



Hint    


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


题解



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

采用了较为暴力的写法

代码


#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;

#define REP(n) for(int o=0;o<n;o++)

const int maxn = 1005;
int edge[maxn][maxn];

inline void road(int a,int b) {
edge[a][++edge[a][0]] = b;
edge[b][++edge[b][0]] = a;
//printf(" %d %d\n",a,b);
}

bool Do() {
int n,m;
if(scanf("%d%d",&n,&m) == EOF)
return false;
for(int i = 1;i <= n;i++)
edge[i][0] = 0;
REP(m) {
int a,b;
scanf("%d%d",&a,&b);
road(a,b);
}
bool can[maxn] = {0};

int cnt = 0;

queue<int> Q;
Q.push(1);

while(!Q.empty()) {
int top = Q.front();
Q.pop();
if(can[top])
continue;
can[top] = 1;
REP(edge[top][0])
Q.push(edge[top][o+1]);
}
/*
printf("===\n");
REP(n)
printf("can[%d]=%d\n",o + 1,can[o + 1]);
*/
while(1) {
bool ok = true;
REP(n) {
if(!can[o + 1]) {
road(1,o + 1);
cnt++;
Q.push(o + 1);
while(!Q.empty()) {
int top = Q.front();
Q.pop();
if(can[top])
continue;
can[top] = 1;
REP(edge[top][0]) {
Q.push(edge[top][o+1]);
}
}
ok = false;
break;
}
}
if(ok)
break;
}
printf("%d\n",cnt);
return true;
}

int main() {
while(Do());
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论