并查集

1. 数组存储的基础实现

此时并查集用一个结构体存储，data 存值（下标+1），parent 存父结点下标
查找操作中先线性查找到需要找到的值，再循环查找其根结点
并操作先找到两合并数组的树根，如果不相等，把一棵树挂到另一棵树根下

#include<iostream>
#include<cstring>
#define MaxSize 1000
typedef int ElementType;
typedef struct{
	ElementType Data; // 存值
	int parent;  // 指向父结点 
}SetType;
using namespace std;

// 查找 
int Find(SetType s[],ElementType x){
	int i;  
	// 找到数组中该值对应的下标 
	for(i=0;i<MaxSize && s[i].Data!=x;i++);
	if(MaxSize <= i) // 如果没有找到，返回 -1 
		return -1;
	// 找到该结点的根结点 
	for(;s[i].parent >= 0;i = s[i].parent); 
	return i; // 返回根结点在数组 s 中的下标 
}

// 并 
void Union(SetType s[],ElementType x1,ElementType x2){
	int root1 = Find(s,x1);  // 找到 x1 的根结点下标 
	int root2 = Find(s,x2);  // 找到 x2 的根结点下标 
	// 如果根结点的下标不同，说明不是一个集合
	if(root1 != root2){   
		s[root1].parent = root2;   // 把 x1 挂到 x2 的集合 
	}
}

int main(){
	SetType s[MaxSize];
	// 初始化数组，父结点全部指向 -1 
	for(int i=0;i<MaxSize;i++){
		s[i].Data = i+1;
		s[i].parent = -1;
	}
	cout<<Find(s,5)<<endl;
	Union(s,3,5);
	cout<<Find(s,4)<<endl;
	cout<<Find(s,3)<<endl;
	Union(s,1,3);
	Union(s,2,4);
	Union(s,8,6);
	cout<<Find(s,6)<<endl;
	cout<<Find(s,8)<<endl;
	return 0;
}

2. 优化存储结构

观察上面的结构体，其实值和数组下标差一，那可以直接把值 1 ~ n 映射为下标的 0 ~ n-1
查找操作直接去找其父结点
并操作直接把一棵树挂另一棵树上去

#include<cstdio>
#include<iostream>
#define MaxSize 10005
typedef int SetType; 
using namespace std;
// 初始化 
void Init(SetType s[]){
	for(int i=0;i<MaxSize;i++)
		s[i] = -1;
}

// 查找 
int Find(SetType s[],int x){
	// 直接去找父结点 
	for(;s[x]>=0;x = s[x]); 
	return x;
} 

// 并
void Union(SetType s[],int x1,int x2){
	// 直接合并 
	s[x1] = x2;
} 

int main(){
	// 此时数组下标既做下标又存值，数组值存父结点下标 
	SetType s[MaxSize];
	Init(s);
	cout<<Find(s,5)<<endl;
	Union(s,3,5);
	cout<<Find(s,4)<<endl;
	cout<<Find(s,3)<<endl;
	Union(s,1,3);
	Union(s,2,4);
	Union(s,8,6);
	cout<<Find(s,6)<<endl;
	cout<<Find(s,8)<<endl;
	return 0;
}

3. 按秩归并优化 Union

当多次并操作时，其中一个操作数固定，另一个操作数一直递增或一直递减时，树会退化成单链表

1. 根据树高归并

一种解决办法是每次将 “矮” 的树挂到 "高"树上去
树高信息存储在根结点的数组值中（之前根结点的数组值都存的 -1，现在存 -树高）
这样当"矮"树挂到"高"树上，树的高度不会增加，只有当两棵树一样高，高度才+1

// 并，假设此时 x1 x2 已经分别是根
void Union(SetType s[],int x1,int x2){
	// x1 更高，负数啊！ 
	if(s[x1] < s[x2]){
		s[x2] = x1;
	}else{
		// 树高相等 
		if(s[x1] == s[x2])
		   s[x2]--;  // 树高 +1 ，是负数 
		s[x1] = x2;
	}
}

2. 根据规模归并

另一种解决办法是规模小的树挂到规模更高的树上去
规模信息存储在根结点的数组值中（之前根结点的数组值都存的 -1，现在存 -元素个数）
这样当小树挂到大树上，只有较少的树会高一层

// 并，假设此时 x1 x2 已经分别是根
void Union(SetType s[],int x1,int x2){
	// x1 规模更大，负数啊！ 
	if(s[x1] < s[x2]){
		s[x1] += s[x2];    // 两树合并，规模相加 
		s[x2] = x1;   // x2 挂到 x1 上 
	}else{
		s[x2] += s[x1];   // 两树合并，规模相加 
		s[x1] = x2;
	}
}

4. 路径压缩优化 Find

查找不可避免的越查越深，路径压缩可以把待查找结点与根结点之间的一系列结点的上一结点都变为根结点，即当查找 D 后：

// 查找 
int Find(SetType s[],int x){
	if(s[x] < 0)  // 本身已经是根 
		return x;
	else  // 1. 找到根 2. 把根变成 x 的父结点 3.再返回根 
		return s[x] = Find(s,s[x]);
}

5. 练习题

File Transfer