ขนาดคอมโพเนนต์ใหญ่สุดตามตัวหารร่วมใน C++

คำอธิบายปัญหา

ให้อาร์เรย์ A ของจำนวนเต็มบวกไม่ซ้ำ สร้างกราฟ: โหนดคือ A[i] มีเส้นเชื่อม A[i]-A[j] ถ้ามีตัวหารร่วม > 1 หาขนาด connected component ใหญ่สุด

ตัวอย่าง

A = [4,6,15,35] → Output: 4
4-6 (gcd=2), 6-15 (gcd=3), 15-35 (gcd=5) → เชื่อมต่อทั้งหมด

แนวทางแก้ปัญหา: Union-Find (DSU) บนตัวหารเฉพาะ

1. สำหรับแต่ละจำนวน x ใน A แยกตัวประกอบเฉพาะ
2. ใช้ map m: prime_factor → index ของจำนวนแรกที่มีตัวประกอบนี้
3. Union index ปัจจุบันกับ index ใน map
4. ติดตามขนาด component ด้วย rank array

รายละเอียด

• แยกตัวประกาะจน sqrt(x)
• ถ้า x เหลือ > 1 หลังลูป → x เองเป็นเฉพาะ
• Union by rank + Path compression

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    vector<int> parent, rank;
    
    int find(int x) {
        return parent[x] == -1 ? x : parent[x] = find(parent[x]);
    }
    
    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if(px == py) return;
        if(rank[px] >= rank[py]) {
            rank[px] += rank[py];
            parent[py] = px;
        } else {
            rank[py] += rank[px];
            parent[px] = py;
        }
    }
    
public:
    int largestComponentSize(vector<int>& A) {
        int n = A.size();
        parent.assign(n, -1);
        rank.assign(n, 1);
        unordered_map<int,int> m;
        int ret = 0;
        
        for(int i=0; i