用java或c++实现，可以分开做a和b(300)

+++++++++ ++++++++++++ +++++++++++ ++++++++++ ++++++++++ ++ +++++++++ ++ ++++ +++ ++ +++++ ++ ++ + + +++++ ++ ++ + ++++ ++ ++++++ +++++ + ++++ ++++++++ +++ ++++++ +++++ + ++++++ ++++++++++ +++++ +++++++ +++ + +++++++++++++++ +++++ ++++++++ ++ + + +++++++++++++++++ +++ +++++++++ +++ ++ ++++++++++++++++++ ++ ++++++++++ + +++ + +++++++++++++++++++ +++ +++++++++++ + ++ +++ ++++++++++++++++++ + +++ ++++++++++++ + + ++ ++++++++++++++++++ + ++++ +++++++++++++ ++++ ++ +++++++++++++++++++++ ++++ ++++++++++++++ +++++ ++++++++++++++++++++++ ++++ ++++++++++++++ ++++++ +++++++++++++++++++++ ++++ +++++++++++++ ++++++++++++++++++++++++++ ++++ +++++++++++++ +++ ++++++++++++++++++++ ++++ ++++++++++++ +++ ++++++++++++++++ ++ ++++ ++++++++++++ + +++++++++++++++++++ +++++ ++++++++++++ + +++++++++++++++++++ +++++ +++++++++++ +++++++++++++++++++ + + +++++ +++++++++++ ++++++++++++++++++++ +++++ +++++ +++++++++++ +++++++++++++++++++ ++++ +++++++ +++++++++ ++++++++++++++++++++ +++++++++++ +++++++++ +++++++++ +++++++++++++++++++ ++++++++++ + +++++++++++ +++++++++ ++++++++++++++++++ +++++++ +++++ ++++++++++++ ++++++++ ++++++++++++++++++ +++++++ +++++ +++++ +++++++ ++++++++ +++++++++++++++++ +++++++ ++++ + ++ +++++++ ++++++++ ++++++++++++++++ + +++ +++ ++++++++ +++++++ +++++ ++++++++++ + ++ +++ ++++++++++ +++++++ ++++++ +++++++++ +++ ++ +++++++++ +++++++ ++++++ ++++++++ ++++ ++ ++++++++ +++++++ +++++ ++++++++ ++++ ++ ++++++++ +++++ +++++++ +++++++ +++++ + ++++++++ +++++ +++++++ ++++ ++++++ + ++++++++ +++++ ++++++++++++++ ++++++ ++ +++++++ ++++ +++++++ + ++ +++++++ ++ ++++++++ ++++ +++++++ +++++ ++++++++ ++ +++++++ ++++ +++++ +++++ +++++++++ ++ + ++++++++ +++ ++++++++++ ++++++++++ ++ ++ +++++++++ ++ +++++ ++++ +++++++++++ +++++++ +++++++++ ++ ++++++++++ +++++++++++ ++++ ++++++++++ ++ + +++++ + +++++++++++++ ++++++++++ + +++++ + +++++++++++++ ++++++++++ + +++++ + ++++++++++++++ +++++++++++ + ++ ++ +++++++++++++++ +++++++++++ ++ + +++++++++++++++++ +++ +++++ +++ +++++++++++++ ++ + +++++++++++++++++ ++++++++++ ++ +++++++++++++ + + +++++++++++++++++++ +++++ ++++++++++++++ + ++++++++++++++++++++ ++++ ++++++++++++++ +++++++++++++++++++++ ++++++ +++++++++++++++ ++ +++++++++++++++++++++++ +++++++++++++++ ++ +++++++++++++++++++++++ ++++++++++++++++ +++ +++++++++++++++++++++++++ ++++++++++++++++ +++++++++++++++++++++++++++++ ++++++++++++++++ +++++++++++++++++++++++++++ +++++++++++++++++ + ++++++++++++++++++++++++ ++++++++++++++++ ++ + ++ ++++++++++++++++++++++ +++++++++++++ +++++ ++++ +++++++++++++++++++++++ ++++++++++++ +++++++++ + ++++++++++++++++++++++ ++++++++++ +++++++ ++ +++++++++++++++++++++ +++++++++ ++++ + + ++++++++++++++++++++ ++++++ ++ + +++++++++++++++++++++ ++++++ ++ ++ +++++++++++++++++++ +++++ +++ ++ ++++++++++++++++++ ++++ +++ ++ +++++++++++++++++++ ++++ 1. Finding connected components in a binary image.a) An Union-Find data structure should be implemented as an abstract data type (a class in C++) with the following operations. • uandf: constructs an union-find data type with n elements, 1, 2, . . . , n.• make set(i): creates a new set whose only member (and thus representative) is i.• union sets(i,j): unites the dynamic sets that contains i and j, respectively, into a new set that is the union of these two sets.• find set(i): returns the representative of the set containing i.• final sets(): returns the total number of current sets, finalizes the current sets (make set() and union sets() will have no effect after this operation), and resets the representatives of the sets so that integers from 1 to final sets() will be used as representatives.b) Design and implement (a program) an algorithm to find the connected components in a binary image using Union-Find data structure in a).An ASCII file containing a binary image is available (see girl.img and img readme) as the input of your program. The output of the program should be the following in this specified order: 1. the input binary image, 2. the connected component image where each component is labelled with a unique character, 3. a list sorted by component size, where each line of the list contains the size and the label of a component,4. same as 2 with the connected component whose size equals to one removed.关于图的说明：File girl.img contains a 71 by 71 binary image in plain text.In this file, a + means 1 and a space means 0. We only consider the connected components of 1. The total number of components is less than 26. Therefore you can use letters from 'a' to 'z' to identify all the components.We use 4 connectivity for +. Therefore ++ and + are considered connected. However + and + are not considered connected.关于make(i)：make xi a subset and assigns a name for the subset.find set(i): returns the name of the subset that contains xiunion(i, j): combines subsets that contain xi and xj, say Si and Sj, into a new subset with a unique name( any name distinct from other names will).

1. Finding connected components in a binary image. 找出图中的相邻部分。a) An Union-Find data structure should be implemented as an abstract data type (a class in C++) with the following operations. 利用Union-Find数据结构设计一个抽象数据类型（如：C++中的类），并定义下列操作。 • uandf: constructs an union-find data type with n elements, 1, 2, . . . , n.构建一个包含n个元素的union-find数据类型• make set(i): creates a new set whose only member (and thus representative) is i.创建一个新的集合，其中唯一的元素是i• union sets(i,j): unites the dynamic sets that contains i and j, respectively, into a new set that is the union of these two sets.分别将包含i和j的动态集合合并，生成一个联合了这两个集合的新集合。• find set(i): returns the representative of the set containing i. 返回包含i的集合的名字• final sets(): returns the total number of current sets, finalizes the current sets (make set() and union sets() will have no effect after this operation), and resets the representatives of the sets so that integers from 1 to final sets() will be used as representatives.返回最终找到的这些集合（此时make set（）和union set（）操作失效），重新用整数编号b) Design and implement (a program) an algorithm to find the connected components in a binary image using Union-Find data structure in a).设计和实现这个算法，找出所给图中的相邻部分。An ASCII file containing a binary image is available (see girl.img and img readme) as the input of your program. The output of the program should be the following in this specified order: 名为girl.img 作为程序的输入。然后按照下列要求输出结果。1. the input binary image, 输入的图2. the connected component image where each component is labelled with a unique character, 将找到的每个相邻部分用一个字符命名3. a list sorted by component size, where each line of the list contains the size and the label of a component,一个根据component大小（包含元素的多少）排序的list，list包含component的大小和命名。4. same as 2 with the connected component whose size equals to one removed. 将component大小是1（只包含一个元素）的删除。关于图的说明：File girl.img contains a 71 by 71 binary image in plain text.In this file, a + means 1 and a space means 0. We only consider the connected components of 1. 图中加号代表1，空格代表0，只考虑相邻的1。The total number of components is less than 26. Therefore you can use letters from 'a' to 'z' to identify all the components. 总共的组成部分少于26，所以可以利用'a' 到 'z'来标识所有个componentWe use 4 connectivity for +. Therefore ++ and + are considered connected. + 认为并排的＋＋是相连的，＋和正下方的＋是相连的。 However + and + are not considered connected. 而斜下方的＋是不相连的。+ +关于make(i)：make xi a subset and assigns a name for the subset. 生成一个包含xi的的子集合，并给它命名。find set(i): returns the name of the subset that contains xi 返回包含xi的子集合的名字。union(i, j): combines subsets that contain xi and xj, say Si and Sj, into a new subset with a unique name( any name distinct from other names will). 合并包含xi的集合，和包含xj的集合

An Union-Find data structure should be implemented as an abstract data type (a class in C++) with the following operations. 利用Union-Find数据结构设计一个抽象数据类型（如：C++中的类），并定义下列操作。 •
uandf: constructs an union-find data type with n elements, 1, 2, . . . , n.构建一个包含n个元素的union-find数据类型•
make set(i): creates a new set whose only member (and thus representative) is i.创建一个新的集合，其中唯一的元素是i•
union sets(i,j): unites the dynamic sets that contains i and j, respectively, into a new set that is the union of these two sets.分别将包含i和j的动态集合合并，生成一个联合了这两个集合的新集合。•
find set(i): returns the representative of the set containing i. 返回包含i的集合的名字•
final sets(): returns the total number of current sets, finalizes the current sets (make set() and union sets() will have no effect after this operation), and resets the representatives of the sets so that integers from 1 to final sets() will be used as representatives.返回最终找到的这些集合（此时make set（）和union set（）操作失效），重新用整数编号

[8D]反对帮人做作业，除非有现金可拿

我也反对，只是有点急

我觉得这样可以交流经验