1.5.5 #

解答 #

$10^6$ 条连接 = $10^6$ 组输入。

对于 quick-find 算法，每次 union() 都要遍历整个数组。

因此总共进行了 $10^9 \times 10^6 = 10^{15}$ 次 for 循环迭代。

每次 for 循环迭代都需要 $10$ 条机器指令，

因此总共执行了 $10 \times10^{15} = 10^{16}$ 条机器指令。

已知计算机每秒能够执行 $10^9$ 条机器指令，

因此执行完所有指令需要 $10^{16} / 10^9 = 10^7$ 秒 = $115.74$ 天。