#include<stdio.h>
#include<stdlib.h>
#ifndef _DisjSet_H
typedef int DisjSet[NumSets+1];
typedef int setType;
typedef int ElementType;
void Initilialize(DisjSet S);
setType Find_semplice(ElementType x,DisjSet s);
setType Find_path_compression(ElementType x,DisjSet s);
void SetUnion_semplice(DisjSet s,setType Root1,setType Root2);
#endif _DisjSet_H
void Initilialize(DisjSet s)
{
for(int step=1;step<NumSets+1;step++)
}
setType Find_semplice(ElementType x,DisjSet s)
{
if(s[x]<1) return x;
else
return Find(s[x],s);
}
setType Find_path_compression(ElementType x,DisjSet s)
{
if(s[x]<1) return x;
else
return s[x]=Find(s[x],s);
}
void SetUnion_semplice(DisjSet s,setType Root1,setType Root2)
{
s[Root2]=Root1;
}
void SetUnion_number(DisijSet s,setType Root1,setType Root2)
{
if(s[Root1]<s[Root2]) // 1树容量更大
{
s[Root1]+=s[Root2]; // 增加树容量
s[Root2]=Root1;
}
else
{
s[Root2]+=s[Root1];
s[Root1]=Root2;
}
}
void SetUnion_deep(DisijSet s,setType Root1,setType Root2)
{
if(s[Root1]<s[Root2]) s[Root2]=Root1;
else
{
if(s[Root1]==s[Root2])
s[Root2]--;
s[Root1]= Root2;
}
}