題目連結

前言

• 難度: hard
• tag: 並查集、數論

這題會需要一些先被知識，再來寫會比較好(關於並查集如果有空再分享，最進有點懶XD)

解題

• 題目要求我們將nums裡的數字，如果有公因數(>1)就串起來，如果最後可以形成一連串，且沒有烙單的數字就回傳true否則false

所以我們要做的就是，看看數字間有沒有關聯，並將其串成一串

如果這麼簡單就好了 (\～￣▽￣)\～

• 但是因為這題的串連方式是去找公因數，如果真的一對一對去串，鐵定時間複雜度會爆炸

想法

舉個例子，4與6可以串聯，因為

• 4的因數: 1 2 4
• 6的因數: 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 原神啟動 on
class 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;
    }
};