1.5.6 #

解答 #

加权 quick-union 算法最多只需要 $lgN $次迭代就可以完成一次 union()。

因此按照上题思路，总共需要 $(lg(10^9) \times 10^6 \times 10) / 10^9 = 0.299$ 秒。