# Todai Entrance Exam: Subject 2010 – Problem 3

**(1)**

Skip

**(2)**

A worst-case example:

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 .

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.