if we make sure there is only one copy of each setwe can determine if two sets are the same or not in ( time as well we can just compare their references to see whether they are the same set or not the keyword is in python will accomplish this so if we want to know that and refer to the same set we can write is and this operation is ( the third operation requires forming new set from the previous two this operation will be performed | |- times in the worst case the first time this operation occurs vertex will be added to an existing set the second timetwo vertices will be added to an existing setand so on so in the endthe overall worst case complexity of this operation is (| | assuming once again that the graph is connected clearlythis is the expensive operation of this algorithm the next section presents data structure that improves on this considerably the partition data structure to improve on the third required operationthe merging of two sets into one seta specialized data structure called partition may be used the partition data structure contains list of integers with one entry for each vertex initiallythe list simply contains list of integers which match their indices , , , , , , , , , , , , , , , , , , , , think of this list as list of treesrepresenting the sets of connected edges in the spanning forest constructed so far tree' root is indicated when the value at location within the list matches its index initiallyeach vertex within the partition is in its own set because each vertex is the root of its own tree discovering the set for vertex means tracing tree back to its root consider what happens when the edge from vertex to vertex is considered for adding to the minimum weighted spanning tree as pictured in fig the partition at that time looks like this , , , , , , , , , , , , , , , , , , , , , vertex is not the root of its own tree at this time since is found at index we next look at index of the partition list that position in the partition list matches its value the is in the set ( treerooted at location looking at vertex nextindex in the list contains index in the list contains vertex is also in the set ( treerooted at index therefore vertex and are already in the same set and the edge from to cannot be added to the minimum spanning tree since cycle would be formed the next edge to be considered is the edge between vertices and the root of the tree containing is at index of the partition the root of the vertex containing is at index as we just saw these two vertices are not in the same set so the edge from to is added to the minimum spanning tree edges this copy belongs to 'acha