畅通工程（并查集）- HDU 1232
Problem Description
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。
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
什么是并查集？
例子：
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
类似上面这种问题，都可以采用并查集来处理。开始的时候每个元素都是一个集合，然后根据一定的关系找到合并的集合，最后进行归类。
基本操作：
初始化init 把每个点所在集合初始化为其自身。
通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。
查找find 查找元素所在的集合，即根节点，find有个小技巧，也就是并查集的路径压缩算法，即在find的过程中直接把子节点指向代表。
合并join 将两个元素所在的集合合并为一个集合。
通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。
解题思路：
这属于并查集的基本题型，可以根据基本的并查集模板求解。
1、至少要修多少道路让所有城市相连；
2、可以判断有多少个城区，保证每个城区中的每个城市都有可以互相连通；
3、若有5个城区就至少要修4条路；
4、有n个至少修n-1条路。
源代码：G++
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<math.h>
#include<string>
using namespace std;
//该数组表示下标为i的城市那部分城区的中心（例pre[3]=5，表示第3个城市的中心为第5个城市）
int pre[1005];
//初始化，最开始的时候每个城市的中心就是自己
void init(int n)
{
int i;
for (i = 1; i <= n; ++i) {
pre[i] = i;
}
}
//用递归函数寻找第x个城市的中心是哪个
int find(int x)
{
//路径压缩算法
if (x != pre[x]) {
//这里只会计算一次，存储在pre[x]中，注意如果数量级很大，不推荐使用递归算法
pre[x] = find(pre[x]);
}
return pre[x];
}
//函数作用：将a，b两个城市归入一个城区
void join(int a, int b)
{
//x，y分别为a，b两个城市所在城区的中心
int x = find(a);
int y = find(b);
if (x != y) {
//将b城市所在城区的中心也变成a城市所在城区的中心，这时候a，b城所在的两个城区就相连了。这两个城区中的每一个城市都有道路可以来往
pre[x] = y;
}
}
int main()
{
int n;
while (~scanf("%d", &n))
{
if (n == 0) break;
int m;
init(n); //初始化
scanf("%d", &m);
int i;
for (i = 1; i <= m; i++)
{
int a, b;
//输入相连的2个城市a，b
scanf("%d%d", &a, &b);
//将a，b连接
join(a, b);
}
//part表示有多少城区
int part = 0;
for (i = 1; i <= n; i++)
{
//如果有个城市的中心是自己，说明这个城市是中心城市。代表这是一个独立的城区，
//因为一个城区的中心只有一个城市。 有多少个中心城市，就有多少个城区。
if (pre[i] == i)
part++;
}
//有n个城区，要让所有城市相连，至少就要多修n-1条路
printf("%d\n", part - 1);
}
return 0;
}