畅通工程

并查集：
并查集是一种树型的数据结构，用来处理不不相交集合的查询以及合并。主要操作有：
1.初始化，即将每一个结点都初始化为一个集合

for(int i = 1; i <= n; i++)
	parent[i] = i;// 初始化每个结点的父结点是自己。

2.查询所在集合，也就是查找跟结点，跟结点是该集合的代表结点

int find(int x){// 返回x的根结点，即x所在集合的代表
	int a = x;
	while(a != parent[a]){
		a = parent[a];
	}
	int i, j;
	i = x;
	//路径压缩，把x以及x的父结点父父结点......全都直接挂到根结点a上。
	while(i != a){
		j = parent[i];
		parent[i] = a;
		i = j;
	}
	
	return a;
}

3.合并，把两个不在同一个集合的元素分别所在的集合合并成同一个集合，可以先调用查询方法判断是否在同一个集合

void join(int x, int y){// 将x，y所在的两个集合合并成同一个集合
	int a = find(x);
	int b = find(y);
	if(a != b){
		parent[a] = b;// 随机把a的父结点令为b
	}
}

例题：畅通工程
题目描述
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。

#include <iostream>

using namespace std;

int parent[1001];


int find(int x){
    int a = x;
    while(a != parent[a]){// 当自己不是自己的父亲的时候，也就是自己还有父节点的时候
        a = parent[a];// 用a一直向上查找，找到x的祖先
    }

    int i, j;
    i = x;

    while(i != a){// 路径压缩，把节点全都直接挂到x的祖先节点上
        j = parent[i];
        parent[i] = a;
        i = j;
    }
    return a;

}


void join(int x, int y){
    int a = find(x), b = find(y);// 分别找到x、y的祖先结点
    parent[a]= b;
}

int main(){
    int city, road;

    while((cin >> city) && city != 0){
        cin >> road;
        int count = 0;
        int x, y;
        for(int i = 1; i <= city; i++){
            parent[i] = i;// 初始化每个结点的父节点都是自己
        }
        for(int i = 1; i <= road; i++){
            cin >> x >> y;// 输入的两个结点之间有路径，说明他们所属于的集合要join到一起
            join(x, y);
        }

        for(int i = 1; i <= city; i++){// 检查有多少个结点的父结点就是自己，也就是说明有多少个集合
            if(parent[i] == i) count++;
        }
        cout << count - 1 << endl;// 要修的路数量就等于集合数减1
    }
    return 0;
}