并查集的应用

 

目录

1.并查集的代码 

2.union操作

3.find操作

4.图

---

写代码：定义一个并查集（用长度为n的数组实现） 
基于上述定义，实现并查集的基本操作—— 并 Union 
基于上述定义，实现并查集的基本操作—— 查 Find 
自己设计一个例子，并查集初始有10个元素，进行若干次Union操作，画出每一次Union后的样子 
自己设计一个例子，基于上一步得到的并查集，进行若干次find操作（每次find会进行“路径压缩”）。画出每次 find （路径压缩）后的样子 

1.并查集的代码 

2.union操作

3.find操作

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100
int UFSets[SIZE];//集合元素数组（双亲指针数组） //初始化操作
void initial(int s[])//s即为并查集 
{for(int i=0;i<SIZE;i++){//每个自成单元素集合 //TODOs[i]=-1;}
} //find操作
int find(int s[],int x) 
{while(s[x]>=0){//循环寻找x的根 //TODOx=s[x];}return x;//根的s[]小于0 
} //union操作
void union(int s[],int root1,int root2)
{if(root1==root2){//TODOreturn;//要求root1和root2是不同的集合 }s[root2]=root1;//将根root2连接到另一根root1下面 
} 
//优化后的union操作
void Union(int S[] ,int Root1,int Root2)
{if(Root1==Root2){//TODOreturn;}if(S[Root2]>S[Root1]){//Root2的结点数更少 //TODOS[Root1]+=S[Root2];//累加集合树的结点总数 S[Root2]=Root1;//小树合并到大树 } else{               //Root1结点数更少 S[Root2]+=S[Root1];//累加到结点总数 S[Root1]=Root2;//小数合并到大树 }
} 
//优化后的find操作
int Find(int S[],int x)
{int root=x;while(S[root]>=0){//循坏找到根 //TODOroot=S[root];}while(x!=root){//压缩路径 //TODOint t=S[x];//t指向x的父结点 S[x]=root;//x直接挂到根结点下面 x=t;}return root; //返回根结点的编号 
} 

4.图