算法复习-并查集union-find

先来看一个实例：
首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整副图的连通性问题。
可能出现的问题：

1. 随意给你两个点，让你判断它们是否连通？
2. 或者问你整副图一共有几个连通分支，也就是被分成了几个互相独立的块？
3. 问再修多少条路，能让整个城镇连通起来，实质就是求有几个连通分支。如果是1个连通分支，说明正副图上的点都连接起来了，不用再修路了；如果是2个连通分支，则只要再修1条路，以此类推。

以上的问题，都是考察并查集的问题。

并查集

并查集(union-find)，从名字就可以看出，主要涉及两种基本操作：合并和查找。这说明，初始时并查集中的元素是不相交的，经过一系列的基本操作（union），最终合并成一个大的集合。
并查集是一种不相交集合的数据结构。
并查集由一个整数型的数组和两个函数构成。数组pre[ ]记录了每个点的前导点是什么，函数find是查找这个元素所在集合的代表元素是什么，join是合并。
这样判断两个元素是否在同一个集合中也是很方便的，只要看find(x)和find(y)是否返回同一个代表元素即可。

find( )函数：

int find(int x) {
    int r = x;
    while (pre[r] != r) 
        r = pre[r];//找到该独立集合的代表结点
    int i = x, j;
    while (i != r) {//路径压缩
        j = pre[i];
        pre[i] = r;//将i的前导结点设置为r根结点，即将所有的叶子节点都连接到根节点上去.
        i = j;
    }
     return r;
}

递归实现：(递归实现比较简单，但可能递归层次太深造成栈的溢出)

int find(int x) {
    if (pre[a] != a)
      pre[a] = find(pre[a]);
    return pre[a];
}

join( )函数：

void join(int x, int y) {
    int a = find(x);
    int b = find(y);
    if (a != b) {
      pre[a] = b;
    }
}

初始化：

for (int i = 0; i < n; ++i) {
    pre[i] = i; //将每一个结点的前导点设置为自己
}

例题：

有n个点，m条边，输入n和m的值，接下来输入m条边分别是（a，b）连接的。求有多少个连通块。例如输入：
4 2
1 2
3 4
输出：2

#include <iostream>
using namespace std;

int pre[1000];

int find_recursively(int a) {
  if (pre[a] != a)
    pre[a] = find_recursively(pre[a]);
  return pre[a];
}

int find(int a) {
  int r = a;
  while (pre[r] != r)
    r = pre[r];

  int i = a, j;
  while (i != r) {
    j = pre[i];
    pre[i] = r;
    i = j;
  }
  return r;
}

void join(int x, int y) {
  int resx = find(x);
  int resy = find(y);
  if (resx != resy)
    pre[resy] = resx;
}

int main() {
  int N, M, a, b, i, res = 0;
  cin >> N;
  cin >> M;

  for (i = 1; i <= N; ++i)
    pre[i] = i;

  for (i = 1; i <= M; ++i) {
    cin >> a;
    cin >> b;
    join(a, b);
  }

  for (i = 1; i <= N; ++i){
    if (pre[i] == i)
      ++res;
  }
  cout<<res<<endl;

  return 0;
}