A worst-case example:
This way, the depth of the tree is decreased by half. Therefore, the worst-case time complexity is:
We pick an edge and then we detect if nodes and are in the same set. If they are, then there exists a cycle in that set. If they aren’t, we add them into the same set and . In this way, the output set will be a spanning tree. The minimum spanning tree is obtained by sorting the edge weights beforehand.