题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1232
并查集入门题。最近在学并查集，它无非包括三个操作：make_set(x)、union_set(x, y)和find_set(x)。
make_set(x)的作用是使得每一个成员x自成一个只包含x的集合。
union_set(x, y)的作用是使x和y合并成为一个新的集合，确定x和y的连通性。
find_set(x)则是查找到x的祖先，这里用set[i]表示元素 i 的祖先，换句话说就是，包含x的集合（唯一）的代表，当然这个代表是集合中的某个成员。对于如何选择代表要具体问题具体分析，但是要注意，如果寻找某一动态集合的代表两次，且在两次之间不修改集合，那么两次得到的答案应该是相同的。
并查集主要是用于确定无向图中连通子图的个数。这条题目实质上就是找出非连通子图的个数，对应的结果就是最少还需要建设的道路数目。
#include <iostream>
using namespace std; const int maxn = ; int set[maxn]; int find_set(int x)
{
int t = x;
while (x != set[x])
{
x = set[x];
}
int j;
while (t != x) // 路径压缩，其实这里不用也行，它是为了处理元素很多或整棵树变为一条链的情况的，可以减少时间复杂度
{
j = set[t];
set[t] = x;
t = j;
}
return x;
} void union_set(int x, int y)
{
x = find_set(x);
y = find_set(y);
if (x != y)
set[x] = y;
} int main()
{
int i, n, m, c1, c2;
while (scanf("%d%d", &n, &m) != EOF && n)
{
for (i = ; i <= n; i++) // make_set(x)
{
set[i] = i;
}
for (i = ; i < m; i++)
{
scanf("%d%d", &c1, &c2);
union_set(c1, c2); // 把c1和c2合并成一个集合，确定它们是连通的
}
int cnt = -;
for (i = ; i <= n; i++) // 注意：cnt是从-1开始的。每个集合都有一个“代表”。假设如果只有一个集合，那么是不再需要建设道路的，至少要有两个代表，才需要建设一条道路
{
if (set[i] == i) // 每得到一个集合的代表，就需要建设一条路，只有一个集合的不需要建设道路！
cnt++;
}
printf("%d\n", cnt);
}
return ;
}