Problem 5: Disjoint sets. Consider a list of cities C1, C2, ..., Cn. Assume we have a relation R such that, for any i, j, R(ci, c) is 1 if cities c; and c; are in the same province, and 0 otherwise. (i) Using a disjoint set data structure, write an algorithm that puts each city in a set such that c; and c; are in the same set if and only if they are in the same province. Justify corectness of your algorithm. (ii) If a disjoint set data structure is implemented by trees and in union the name of the new set is always the name of the larger set, what is the worst-case running time of your algorithm.
Problem 5: Disjoint sets. Consider a list of cities C1, C2, ..., Cn. Assume we have a relation R such that, for any i, j, R(ci, c) is 1 if cities c; and c; are in the same province, and 0 otherwise. (i) Using a disjoint set data structure, write an algorithm that puts each city in a set such that c; and c; are in the same set if and only if they are in the same province. Justify corectness of your algorithm. (ii) If a disjoint set data structure is implemented by trees and in union the name of the new set is always the name of the larger set, what is the worst-case running time of your algorithm.
Question
Transcribed Image Text:Problem 5: Disjoint sets. Consider a list of cities C1, C2, ..., Cn. Assume we have a relation
R such that, for any i, j, R(ci, c) is 1 if cities c; and c; are in the same province, and 0
otherwise.
(i) Using a disjoint set data structure, write an algorithm that puts each city in a set
such that c; and c; are in the same set if and only if they are in the same province.
Justify corectness of your algorithm.
(ii) If a disjoint set data structure is implemented by trees and in union the name of the
new set is always the name of the larger set, what is the worst-case running time of
your algorithm.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
