题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1232

题目描述

某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?

思路

并查集模板题。

AC代码

/*************************************************************************
    > File Name: 1232.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-07-04 Sat 15:12:18 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int Set[1000+10];
int find(int x) { // 找根节点,并压缩路径
    int root = x;
    while(root != Set[root])
        root = Set[root];
    while(x!=root) { // 压缩路径
        int  t = Set[x];
        Set[x] = Set[root];
        x = t;
    }
    return root;
}
void merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy)
        Set[min(fx,fy)] = max(fx, fy); // 合并,小的集合(根节点)往大的合并
}

int main()
{
#ifdef Oj
    freopen("1232.in", "r", stdin);
#endif
    int M, N;
    int x, y;
    while(scanf("%d", &N)==1 && N) {
        scanf("%d", &M);
        for(int i=1; i<=N; ++i)
            Set[i] = i;
        for (int i = 0; i < M; ++i) {
            scanf("%d%d", &x, &y);
            merge(x, y);
        }
        int need = 0;
        for (int i = 1; i <= N ; ++i) {
            if(Set[i] == i)
                ++need;
        }
        printf("%d\n", need-1); // 减去一个根节点
    }
    return 0;
}