题目

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;
}