The girl.img file is shown below:

+++++++++ +++ +++++++++ +++ ++++++++ +++ +++++++ ++++ ++++++ ++ ++++ +++++ ++ ++++ +++ ++ +++++ ++ ++ + + +++++ ++ ++ + ++++ ++ ++++++ +++++ + ++++ ++++++++ +++ ++++++ +++++ + ++++++ ++++++++++ +++++ +++++++ +++ + +++++++++++++++ +++++ ++++++++ ++ + + +++++++++++++++++ +++ +++++++++ +++ ++ ++++++++++++++++++ ++ ++++++++++ + +++ + +++++++++++++++++++ +++ +++++++++++ + ++ +++ ++++++++++++++++++ + +++ ++++++++++++ + + ++ ++++++++++++++++++ + ++++ +++++++++++++ ++++ ++ +++++++++++++++++++++ ++++ ++++++++++++++ +++++ ++++++++++++++++++++++ ++++ ++++++++++++++ ++++++ +++++++++++++++++++++ ++++ +++++++++++++ ++++++++++++++++++++++++++ ++++ +++++++++++++ +++ ++++++++++++++++++++ ++++ ++++++++++++ +++ ++++++++++++++++ ++ ++++ ++++++++++++ + +++++++++++++++++++ +++++ ++++++++++++ + +++++++++++++++++++ +++++ +++++++++++ +++++++++++++++++++ + + +++++ +++++++++++ ++++++++++++++++++++ +++++ +++++ +++++++++++ +++++++++++++++++++ ++++ +++++++ +++++++++ ++++++++++++++++++++ +++++++++++ +++++++++ +++++++++ +++++++++++++++++++ ++++++++++ + +++++++++++ +++++++++ ++++++++++++++++++ +++++++ +++++ ++++++++++++ ++++++++ ++++++++++++++++++ +++++++ +++++ +++++ +++++++ ++++++++ +++++++++++++++++ +++++++ ++++ + ++ +++++++ ++++++++ ++++++++++++++++ + +++ +++ ++++++++ +++++++ +++++ ++++++++++ + ++ +++ ++++++++++ +++++++ ++++++ +++++++++ +++ ++ +++++++++ +++++++ ++++++ ++++++++ ++++ ++ ++++++++ +++++++ +++++ ++++++++ ++++ ++ ++++++++ +++++ +++++++ +++++++ +++++ + ++++++++ +++++ +++++++ ++++ ++++++ + ++++++++ +++++ ++++++++++++++ ++++++ ++ +++++++ ++++ +++++++ + ++ +++++++ ++ ++++++++ ++++ +++++++ +++++ ++++++++ ++ +++++++ ++++ +++++ +++++ +++++++++ ++ + ++++++++ +++ ++++++++++ ++++++++++ ++ ++ +++++++++ ++ +++++ ++++ +++++++++++ +++++++ +++++++++ ++ ++++++++++ +++++++++++ ++++ ++++++++++ ++ + +++++ + +++++++++++++ ++++++++++ + +++++ + +++++++++++++ ++++++++++ + +++++ + ++++++++++++++ +++++++++++ + ++ ++ +++++++++++++++ +++++++++++ ++ + +++++++++++++++++ +++ +++++ +++ +++++++++++++ ++ + +++++++++++++++++ ++++++++++ ++ +++++++++++++ + + +++++++++++++++++++ +++++ ++++++++++++++ + ++++++++++++++++++++ ++++ ++++++++++++++ +++++++++++++++++++++ ++++++ +++++++++++++++ ++ +++++++++++++++++++++++ +++++++++++++++ ++ +++++++++++++++++++++++ ++++++++++++++++ +++ +++++++++++++++++++++++++ ++++++++++++++++ +++++++++++++++++++++++++++++ ++++++++++++++++ +++++++++++++++++++++++++++ +++++++++++++++++ + ++++++++++++++++++++++++ ++++++++++++++++ ++ + ++ ++++++++++++++++++++++ +++++++++++++ +++++ ++++ +++++++++++++++++++++++ ++++++++++++ +++++++ ++ + ++++++++++++++++++++++ ++++++++++ +++++ ++ ++ +++++++++++++++++++++ +++++++++ +++ + + + ++++++++++++++++++++ ++++++ ++ + +++++++++++++++++++++ ++++++ ++ ++ +++++++++++++++++++ +++++ +++ ++ ++++++++++++++++++ ++++ +++ ++ +++++++++++++++++++ ++++ 

The img_readme file is shown below:

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. + +

. a) A Disjoint-Set data structure should be implemented, with the most efficient algorithm (union by rank and path compression), as an abstract data type (a class in C++ or java) with the following operations. uandf (n): constructs an disjoint-set 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. 0 find_set(i); returns the representative of the set containing i. final_sets(): returns the total number of current sets and finalizes the current sets: (i) make_set() and union sets() will have no effect after this operation and (ii) resets the representatives of the sets so that integers from 1 to final sets() will be used as representatives. b) Design and implement (write a program) an algorithm to find the connected components in a binary image using Disjoint-Set 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 char- acter, 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 components whose sizes are less than three deleted. . a) A Disjoint-Set data structure should be implemented, with the most efficient algorithm (union by rank and path compression), as an abstract data type (a class in C++ or java) with the following operations. uandf (n): constructs an disjoint-set 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. 0 find_set(i); returns the representative of the set containing i. final_sets(): returns the total number of current sets and finalizes the current sets: (i) make_set() and union sets() will have no effect after this operation and (ii) resets the representatives of the sets so that integers from 1 to final sets() will be used as representatives. b) Design and implement (write a program) an algorithm to find the connected components in a binary image using Disjoint-Set 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 char- acter, 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 components whose sizes are less than three deleted