Todai Entrance Exam: Subject 2010 – Problem 3




    \[ O\left (N + \frac{M(M+1)}{2}  \right ) \]

A worst-case example:

    \[ (x, y) = (0, 1), (0, 2), … , (0, M) \]


This way, the depth of the tree is decreased by half. Therefore, the worst-case time complexity is:

    \[ O\left (N + \frac{M(M+2)}{4}  \right ) \]

(4) Reference: 1 & 2.

We pick an edge (x, y) and then we detect if nodes x and y 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 x and y. In this way, the output set will be a spanning tree. The minimum spanning tree is obtained by sorting the edge weights beforehand.


Leave a Reply

Your email address will not be published. Required fields are marked *