Todai Entrance Exam: Subject 2010 – Problem 3




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

A worst-case example:

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

(3) Reference: 3 & 4 & 5.

It is possible to implement path compression and reduce the number of loop iterations in the “find” function. However, a linear tree is still built (and broken after one reference from lower-level nodes) and union by rank is the only way to deal with it. Yet, I cannot find any ways to implement it without touching the “repeat_union” to initialize the rankings to 0.

It’s hard to tell the improved time complexity exactly, in the worst-case scenario it would be O(N + M).

(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 *