东南学院计算机学院方效林

《东南学院计算机学院方效林》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东南大学计算机学院方效林本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件第六章集合与字典本章主要内容并查集2并查集互不相交的集合(等价类的划分)需要经常合并集合(等价类的合并)需要经常查找元素属于哪个集合3并查集并查集支持以下操作初始化UFSets(s):将s中每个元素自成一个集合合并Union(Root1,Root2):集合Root2并入Root1查找Find(x):查找元素x属于哪个集合4并查集用树表示集合初始化时，每个元素自成为一棵树53412567890全集合S初始化时形成的森林初始化时形成的父指针表示负数

2、表示没有父结点-1表示树中有1个结点-2表示有2个结点，以此类推下标父指针-1-1-1-1-1-1-1-1-1-12345671089并查集用树表示集合假设经过若干合并后有3个集合{0,6,7,8}，{1,4,9}{2,3,5}68670集合的树形表示集合的父指针表示235149下标父指针2345671089-321200-3-401并查集用树表示集合合并s1={0,6,7,8}s2={1,4,9}s2作为s1根的子树，或相反78670合并集合81674908167490第一种合并方式第二种合并方式149第一种合并的父指针

3、表示下标父指针2345671089-3202000-700并查集用树表示集合合并s1={0,6,7,8}s2={1,4,9}s2作为s1根的子树，或相反哪一种合并方式好？先介绍查找Find操作Find(4)表示4所属集合，返回值0号结点(即根结点)Find操作时间相当于结点到根路径长度881674908167490第一种合并方式第二种合并方式第一种方式好：查找时间更优合并方式：将结点数更少的集合作为结点数更多的集合的根的子树