王道数据结构打卡（3）------并查集的应用_王道并查集

1.概论

定义：
   并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

主要构成：
   并查集主要由一个整型数组pre[ ]和两个函数union（ ）、join( )构成。数组 pre[ ] 记录了每个点的前驱节点是谁，函数 find(x) 用于查找指定节点 x 属于哪个集合，函数 join(x,y) 用于合并两个节点 x 和 y 。

作用：
  并查集的主要作用是求连通分支数（如果一个图中所有点都存在可达关系（直接或间接相连），则此图的连通分支数为1；如果此图有两大子图各自全部可达，则此图的连通分支数为2……）

2.定义一个并查集

#define max 50
int uset[max];

3.创立集合 

void makeSet(int size)
{
	for (int i = 1; i <= size; i++)
	{
		//各自为各自的代表
		uset[i] = i;
	}
}

即:uset[1]=1,uset[2]=2,uset[3]=3,uset[4]=4,uset[5]=5,uset[6]=6。这意味着，uset[i]的朋友（父节点）是i自己。 

4.实现并查集的基本操作Union

    并查集的实现原理也比较简单，就是用树来表示一个集合，树的每个结点就是集合的一个元素，根节点就是集合的代表。以如下并查集为例。

1.合并(1,2,3,4)，合并(5,6)，分别以1和5作为代表

4.1.代码实现

 
void unite(int x, int y) 
{
	//先找相对应的代表
	int x = find(x);
	int y = find(y);
	if (x == y)
	{
		return;
	}
	uset[x] = y;
}

给出得到两个集合分别构建的合并过程

 合并2和1：分别找到自己的代表，都是自己2和1，显然2!=1，则uset[2]=1，这意味着，uset[2]的朋友是1；
合并3和2：分别找到自己的代表，都是自己3和2，显然3!=2，则uset[3]=2，这意味着3的朋友是2；
合并4和3：分别找到自己的代表，都是自己4和3，显然4!=3，则uset[4]=3，这意味着4的朋友是3；
这样（1，2，3，4）合并完成，此时可以发现它是一棵斜树。

同理，合并（5，6）就不再赘述。

现在，我们假设再合并（4,6）。

合并6和4：分别找到自己的代表5和1，显然5！=1，则uset[5]=1，这意味着5的朋友是3（1作为5的父节点）。

最终合并为同一个并查集结果如上 

5.查询

   find(x)其实就是查找x的代表是谁。查询采用递归的思想，直到代表是自己（访问到根结点），否则就一直找朋友的朋友...find(uset[i])。

5.1.代码实现

int find（int i){
   if(i==uset[i]){
      return i;
   }
   else
     return  find(uset[i]);
}

6.路径压缩

方法：查找时优化

     在每次查找时，令查找路径上的每个结点都指向根结点。

 

 
int find(int i)
{
	if (i == uset[i])
	{
		return i;
	}
	return uset[i] = find(uset[i]);//在第一次查找的时候 将结点直接连到跟
}