并查集的操作

Ryuichi_Home / 2023-05-03 / 原文

//并查集

#include <stdio.h>
#define SIZE 100
int UFSets[SIZE];

void initial(int S[])//初始化并查集 全部设为-1 即每一个元素都是独立的
{
    for(int i=0;i<SIZE;i++)
    {
        S[i]=-1;
    }
}

int Find(int S[],int x)//查找元素操作 返回x所属根节点 x指的是数组下标
{
    while(S[x]>=0)//父节点如果大于等于0说明不是根节点 继续向上查询 如果小于0则说明是根节点 返回x
    {
        x=S[x];
    }
    return x;
}

void Union(int S[],int Root1,int Root2)//并操作 Root1和Root2指的是数组下标
{
    if(Root1==Root2)//如果两个集合是相同的 不可以执行并操作
    {
        return;
    }
    else
    {
        S[Root2]=Root1;//否则 将Root2的父节点设为Root1
    }
}

void BetterUnion(int S[],int Root1,int Root2)//并的优化
{
    if(Root1==Root2)
    {
        return;
    }
    if(S[Root2]>S[Root1])//用绝对值来存储树的结点个数 如-7代表该根结点下有7个结点（包括根结点）
    {
        S[Root1]+=S[Root2];//因为是负数 所以如果S[Root2]>S[Root1] 说明Root2下的结点要少于Root1 将两个树的结点个数相加
        S[Root2]=Root1;//将Root2的根结点指向Root1
    }
    else
    {
        S[Root2]+=S[Root1];
        S[Root1]=Root2;
    }
}

int BetterFind(int S[],int x)//Find算法优化 压缩路径    
{
    int root = x;
    while(S[root]>=0)//找出x结点的根结点并将其赋给root
    {
        root = S[root];
    }
    while(x!=root)//如果x不是根节点的话 就将其直接接到根结点上
    {
        int t=S[x];//先把x原来的位置保存下来
        S[x]=root;//将结点接到根结点上的操作
        x=t;//向上查找父节点 并将其全部接到跟结点上
    }
    return root;
}

int main()
{
    return 0;
}