文字：独木
排版：独木
图片：独木
并查集并查集：一种简单的集合表示。通常用树的双亲表示法作为并查集的存储结构。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数。
Initial(S)将集合S中的每个元素都初始化为只有一个单元素的子集合。Union(S,Root1,Root2)把集合S中的子集合(互不相交)Root2并入子集合Root1.Find(S,x)查找集合S中单元素x所在子集合，并返回该子集合的名字。
下面的结点都是根节点，所以双亲结点都是负数S={0,1,2,3,4,5,6,7,8,9}S0={0},S1={1},S2={2},S3={3},S4={4},S5={5},S6={6},S7={7},S8={8},S9={9}例题：
S={0,1,2,3,4,5,6,7,8,9}S0={0,6,7,8},S1={1,4,9},S2={2,3,5}
解析：S0是根节点，下面有四个子结点（0，6，7，8）所以为-4，S1和S2是根节点下面有三个子结点所以为-3，S4、S5、S6、S7、S8、S9都是子结点所以parent填相应的双亲结点,如S4的双亲结点是s1，表就填1。如下图
#defineSIZEintUFSets[SIZE];//双亲结点下标voidInitial(intS[]){//初始化 for(inti=0;isize;i++) S=-1;}//查找intFind(intS[]，intx){ while(S[x]=0)//如果是正数就不是根节点 x=S[x]; returnx}//合并voidUnion(intS[],intRoot1,intRoot2){ S[Root2]=Root1;}
End
1
发现更多精彩