【Greatest Common Divisor Traversal】leetcode 解题 2/25

题目连结

前言

难度: hardtag: 并查集、数论

这题会需要一些先被知识，再来写会比较好(关于并查集如果有空再分享，最进有点懒XD)

解题

题目要求我们将nums里的数字，如果有公因数(>1)就串起来，如果最后可以形成一连串，且没有烙单的数字就回传true否则false

所以我们要做的就是，看看数字间有没有关联，并将其串成一串

如果这么简单就好了 (\～￣▽￣)\～

但是因为这题的串连方式是去找公因数，如果真的一对一对去串，铁定时间複杂度会爆炸

想法

举个例子，4与6可以串联，因为

4的因数: 1 2 46的因数: 1 2 3 6
因为有共通的因数2，且大于1，所以可以串

这时再加入数字 9

9的因数: 1 3 9
9 会无法与4串联，但可以跟6串联(因数3)，所以会变成这样

父  6   / \  4   9

由这个，可以让我们想到，他们会串联是因为因数相同，所以只要

将这个数字给分解，并留下质因数(以4来说就是2，不包含4)如果这个质因数没有人指向，将其定为父节点，否则指向这个因数的父节点

当下一个数字进入时，重复以上动作:(6)

将数字分解，留下质因数(2,3)找2有没有人指向，发现4已经为父节点，故将6指向4

再重複1次(9)

将数字分解，留下质数(3)找3有没有指向，发现6为父节点，故将9指向6

现在，图应该是这样

父 4    6   |    |    6    9

---

进行merge合併相同指向(应该在找到父节点时就要做，但为了方便讲解放在这里)
*依据rank(规模)*小的合併大的

最后，执行一次跑图(串联)

1. 4(指向自己)2. 6(指向4)3. 9(指向6)4 <-- 6 <--9

依据rank(规模)，小的与大的合併(这里是相同的rank)

结论

这一题我觉得算是中规中矩，有数论也有dsu，当然也有看到有人单纯用数论解(狠人)，如果你有兴趣听我废话解题的话可以加入我们的dc讨论，感谢你的阅读

code(cpp)

code连结

#define 原神启动 onclass Solution {    // DSU    int Find_(vector<int>&f,int x){        if(f[x] != x){            f[x] = Find_(f,f[x]);        }                return f[x];    }    // merge (compress array pointer)    void merge(vector<int>&f,vector<int>&size,int x,int y){        x = Find_(f,x);        y = Find_(f,y);        // if both have same root        if(x == y)return;        // let x rank  >  y rank        if(size[x]<size[y]){            swap(x,y);        }        // 合併        f[y] = x;        // for anwer        size[x]+=size[y];    }public:    bool canTraverseAllPairs(vector<int>& nums) {                const int n = nums.size();                if(n == 1) return true;        // create a dsu board        vector<int> f(n),size(n);        for(int i=0;i<n;i++){            //root is thierself             f[i] = i;                        //all size = 1            size[i] = 1;        }        // store the point is root        map<int,int> have;                //find common root        for(int i=0;i<n;i++){            int num = nums[i];            if(num==1)return false;            for(int d = 2;d * d <= num;d++){                            if(num % d == 0){                    if(have.count(d)) merge(f,size,i,have[d]);                    else have[d] = i;                    while(num % d == 0) num/= d;                 }            }            if(num > 1){                            if(have.count(num)) merge(f,size,i,have[num]);                else have[num] = i;            }        }              return size[Find_(f,1)] == n;    }};