# Todai Entrance Exam: Subject 2010 – Problem 3

**(1)**

Skip

**(2)**

A worst-case example:

**(3)**

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.