一个类似union find题目请教

面试时候碰到的一个题，给一组>1的数字，如果两个数字不是co prime就认为有一条边，比如2和4，然后就会形成一些connectted components，问这些connected components的最大size。
我说了bfs这样，然后问有没有更优方法，我说了union find，面试官同意这个思路，但是说利用union find类似的可以做到linear time，我就不知道怎么做了，不知道大家可有比较好的思路？

一个想法，不过还是没办法做到线性
对于每一个数，分解质因数，然后把所有碰到的质因数收集起来，标上新的标号（从n+1开始
然后合并，比如把12跟2和3合并，30跟2 3 5合并
合并的时候维护下每个集合的大小，注意新标号的初始siz为0，别的为1
复杂度大概n再乘个根号n的样子？

https://leetcode.com/problems/la ... e-by-common-factor/

337845818 发表于 2019/10/31 11:44:09
https://leetcode.com/problems/largest-component-size-by-common-factor/

非常感谢 竟然是lc原题……

补充一下，我感觉lc最高票的几个答案，也不是严格意义的o(n)的，感觉面试官说的不是很准确