题目描述如下：
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
输入：第一行给出两个整数， 分别是城镇数目N(<1000)和道路数目M, 随后的M行对应着M条道路，每行给出一对正整数。， 分别表示这条道路连通的两个城市的编号。 为简单起见， 城镇编号从1到N。 注意， 两个城市之间可以有多条道路联通。 如下：
3 31 21 22 1当N为0时， 输入结束， 该例子不用处理。 输入文件如下：4 2 1 3 4 33 3 1 21 3 2 3 5 2 1 2 3 5999 0 输出文件如下：0 2 998 分析：
该题考察的是并查集的运用。 即求整幅图的连通性问题。 也就是说， 这幅图有几个联通分支。
如果是一个连通分量， 说明整幅图的点都连接起来了， 不用再修路了。 如果有两个连通分量， 则只需要修一条路。 从这两个连通分量中分别任意选取一个点 ， 连接起来即可。 如果有n 个连通分量， 只需再修n -1 条路即可。
下面利用并查集合求解如下：
#include <iostream>#include <fstream>using namespace std;const int MAX = 1000 + 5;int parent[MAX];void Make_Set(int N) {for(int i = 1; i <= N; ++i) {parent[i] = i;}}int Find_Set(int x) {while(parent[x] != x) { // 找到x 所在集合的代表元素x = parent[x];}return x;}void UNION(int x, int y) {int rootX = Find_Set(x);int rootY = Find_Set(y);if(rootX != rootY) {parent[rootX] = rootY;}}int main() {int N, M, x, y, res;ifstream input("in.txt");ofstream output("out.txt");while(input >> N >> M) {Make_Set(N);for(int i = 1; i <= M; ++i) {input >> x >> y;UNION(x, y);}res = 0;for(int i = 1; i <= N; ++i) { // 统计连通分量个数if(parent[i] == i) {res++;}}output << res – 1 << endl;}return 0;}运行结果如下：
优化办法：
对于并查集， 有两种优化策略。
优化策略1： 按秩合并策略。 这一优化是针对合并的。 作用是避免了合并时产生糟糕的情况。 方法是将深度小的树合并到深度达的树。
假设两个树的深度分别为 h1 和 h2， 则合并后树的高度h 如下：
if(h1 != h2) max(h1, h2)
if(h1 == h2) h1 + 1
效果是使得合并之后， 包含k个节点的树的最大高度不超过 floor(logk)。
进一步优化： 优化策略是路径压缩。 是针对Find进行优化的。 通过路径压缩， 可以减少每次寻找根节点的次数， 使得我们的树更加的flat。
步骤： 第一步找到根节点
第二步， 修改查找路径上的所有节点，， 将他们只想根节点。
优化之后的程序如下：
#include <iostream>#include <fstream>using namespace std;const int MAX = 1000 + 5;struct Node {int parent;int Rank;};Node node[MAX];void Make_Set(int N) {for(int i = 1; i <= N; ++i) {node[i].parent = i;node[i].Rank = 0;}}int Find_Set(int x) { // 查找所属集合并压缩搜索路径if(x == node[x].parent) { // 找到x 所在集合的代表元素return x;}elsenode[x].parent = Find_Set(node[x].parent);return node[x].parent;}void UNION(int x, int y) {int rootX = Find_Set(x);int rootY = Find_Set(y);if(rootX == rootY) return; // 同一个集合中else {if(node[rootX].Rank == node[rootY].Rank) {node[rootX].parent = rootY;node[rootY].Rank++;}else if(node[rootX].Rank > node[rootY].Rank)node[rootY].parent = rootX;elsenode[rootX].parent = rootY;}}int main() {int N, M, x, y, res;ifstream input("in.txt");ofstream output("out.txt");while(input >> N >> M) {Make_Set(N);for(int i = 1; i <= M; ++i) {input >> x >> y;UNION(x, y);}res = 0;for(int i = 1; i <= N; ++i) { // 统计连通分量个数if(node[i].parent == i) {res++;}}output << res – 1 << endl;}return 0;}运行后结果同上。
要么读书、要么旅行，灵魂和身体，必须有一个在路上。
