/*
今天读了一种叫做并查集的数据结构，以前做题做到了，但一些解题报告质量参差不齐，
自己只是理解个大概了，不知道怎么防止退化，怎么路径压缩。
也可能是因为之前接触了一些，今天看书才都理解了。学习一个知识点还是应该系统的学一下比较好。
并查集是一种用来处理分组的数据结构，在逻辑上可以看成树形结构，但我们可以用数组来实现。
它能比较方便的查询元素a和元素b是否在同一个分组内，还有合并两个分组的操作。
一个一维数组即可，刚开始初始化为a[i]=i;说明每个元素各成一组，每当有两个元素x和y连接起来的时候先查询是否在一组内，
不在一组的话进行a[x]=y；操作，即把x的父节点改为y。
优化1：可以防止树形结构退化成类似链表的线性结构。
加一个数组rank[]，储存当前组的深度，每次进行合并操作前都比较两组的深度，把深度小的加到深度大的那一组，
这样可以让树的深度尽量保持在logn。
优化2：每次查找一个数查找到他的父节点之后，把一路查到的元素的父节点都直接改成根节点，
这样最后这个组所组成的树只有一层。（为了方便，深度还是按以前的算即可）
*/
#include
#include
#define MAX_N 99999999
using namespace std;
int par[MAX_N+1];//父节点
int depth[MAX_N+1];//深度
void init(){
for(int i=0;i<=MAX_N;i++){
par[i]=i;
depth[i]=1;
}
}
int find_father(int t){
if(t==par[t]){
return t;
}else{
return par[t]=find_father(par[t]);
//实现了路径压缩
}
}
void unite(int t1,int t2){
int f1=find_father(t1);
int f2=find_father(t2);
if(f1==f2){
return ;
}
if(depth[f1]
par[f1]=f2;
}else{
par[f2]=f1;
if(depth[f1]==depth[f2]){
depth[f1]++;
//记录深度
}
}
}
int main()
{
return 0;
}
网友评论