了解 Leetcode: 1627. Graph Connectivity With Threshold 那两层For回圈

再重新叙述一次问题：

假设n = 878，代表说现在给你1到878个点，在没有资讯前，你看每个点都是一座孤岛，但只要俩俩孤岛的编号满足两者的公因数z大於阈值(threshold)，就代表他俩有连线。

接着就是问你在找到这878个孤岛之间的连线後，我给你俩俩孤岛的编号，问你我能不能从孤岛4走到孤岛877啊？麻烦快点告诉我谢谢。
　
　
　
　

回圈的意义

这个回圈在做的事情就是找此时点与点之间的连线，用并查集的做法意味着：我不需要知道我要怎麽走才能从点4走到点877，我只要知道点4跟点877是都有跟同一个点连线就行，因为这样代表他们之间也有连线，也就代表我能从点4走到点877。

for (int z = threshold + 1; 2*z <= n; z++)
    for (int m = 2; m*z <= n; m++) 
        unionfunc(z, m*z);

那麽for的起始条件以及终止点条件的设定由来？

有个条件

z > threshold

z就是公因数，也是开始找的孤岛编号，假设n = 878，threshold = 95，代表说我要找的公因数，必须大於threshold，从96开始，也代表说孤岛1～孤岛95不可能有连线，因为他们没有大於等於96的因数。

所以第一层回圈起始条件设为这样

z = threshold + 1

　
　
再来是终止条件。

10
= 1 x 10
= 2 x 5
= 5 x 2
= 10 x 1

像是在找10的因数时，不需要全部找完，只要找到一半，因数相乘互换的部分，就可以找到所有10的因数，而中止点恰好是10/2。所以在878个孤岛中，从threshld+1的编号开始找时，只需要去找z <= 878/2的编号就行。 那因为除法比乘法慢，所以改成等价的

2*z <= n

第一层for已经帮我确认过z是大於threshold的。再来，题目说，若孤岛俩俩的编号同时具有z这个因数，他们就有连线。

什麽时候会有相同的因数？z的倍数保证他一定也有z的因数，所以从编号96与编号2*96，和编号3*96..之间一定有连线。所以这里就把孤岛96和小於孤岛总数的96倍数，连接起来，因此起始与终止条件设为

m = 2; m*z <= n

虽然常常感叹他们都是怎麽想到这些解法的，但哟西哟西，又了解了一点东西。
　
　
　

参考：
https://leetcode.com/problems/graph-connectivity-with-threshold/discuss/933034/RubyPython-Union-Find-with-explanation.-Short-code.