并查集，是利用树的思想 题目：某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
输入帮助：测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说 3 3 1 2 1 2 2 1 这种输入也是合法的 当N为0时，输入结束，该用例不被处理。
简要的思路，假如两个城镇建立起一条路，把一个城镇作为子节点，一个作为父节点。 每次输入两个城镇时，都需要找到根节点，对比根节点，这样才能确保两棵树是独立的树，没有连接， 假如两个根节点不同，就结合两个根节点节点。合并为一棵树。这样这棵树的所有节点都有一个根节点，即所有节点都可以互相到达。最后计算根节点的个数n，n-1即为最小需要的路径。
其中还运用了，路径压缩，即在找出根节点时，把根节点下的所有节点，连接到最大根节点。
#include <iostream> #include<iomanip> using namespace std; int pra[1001] = {0}; int find(int root)//findroot函数，用于查找输入数值的根。并压缩路径 { int son, temp; son = root; while (root != pra[root])//寻找最大根 { root = pra[root]; } while (root != pra[root])//压缩路径的方式，将输入值与之后的跟直接连到最大根处； { temp = pra[son]; pra[son] = root; son = temp; } return root;//返回最大根 } void unite(int x, int y)//根的连接 { x = find(x);//找到x和y的最大根； y = find(y); if (x != y)//如果两个的最大根不相同，那么就将其中一个最大根作为子根连接到一个最大根，根的合并 { pra[x] = y; } } int main() { int n, k; int num; while (cin >> n) { if (n == 0) break; else { cin >> k; num = n - 1; for (int i = 1; i <= n; i++) pra[i] = i; for (int i = 1; i <= k; i++) { int x, y; cin >> x >> y; unite(x, y); } for (int i = 1; i <= n; i++) { if (pra[i] != i) num--;//遍历边的条数，计算最少要几条边 } cout << num << endl; } } }