Simplest Union Find Solution with Inline Comments for Explaination (95% Time)
Main Intuition:\n1. Do union operation of all numbers with their prime factors\n2. Answer will be the most frequent parent (or root)\n\n    /* -----------------
**Main Intuition:**\n1. Do union operation of all numbers with their prime factors\n2. Answer will be the most frequent parent (or root)\n```\n    /* --------------------------------- GENERAL UNION FIND TEMPLATE ----------------------------------- */\n    \n    struct vt{\n        int parent;\n        int rank;\n    };\n    \n    int ds_find(vector<vt> & ds, int v){\n        if(ds[v].parent==-1)\n            return v;\n        \n        return ds[v].parent = ds_find(ds, ds[v].parent);\n    }\n    \n    void ds_union(vector<vt> & ds, int v1, int v2){\n        if(ds[v1].rank < ds[v2].rank)\n            ds[v1].parent = v2;\n        \n        else if(ds[v1].rank > ds[v2].rank)\n            ds[v2].parent = v1;\n        \n        else{\n            ds[v1].parent = v2;\n            ds[v2].rank++;\n        }\n    }\n    \n    /* ------------------------------------------------------------------------------------------------- */\n    \n    int largestComponentSize(vector<int>& nums) {\n        int mx = *max_element(nums.begin(), nums.end());\n        \n        vector<vt> ds (mx+1, {-1, 0});\n        \n        /* Iterate array nums */\n        \n        for(int num : nums){\n            int sqr_root = sqrt(num);\n            \n            /* For each element, find prime factors (by iterating from 2 to sqrt(num)) */\n            \n            for(int i=2; i<=sqr_root; i++){\n                \n                /* Do union operation of num with its every prime factor */\n                \n                if(num%i==0){\n                    \n                    /* We need to do find operation everytime because root may change anytime */\n                    \n                    int root1 = ds_find(ds, num);\n                    int root2 = ds_find(ds, i);\n                    \n                    if(root1!=root2)\n                        ds_union(ds, root1, root2);\n                    \n                    root1 = ds_find(ds, num); \n                    root2 = ds_find(ds, num/i);\n                    \n                    if(root1!=root2)\n                        ds_union(ds, root1, root2);\n                }\n            }\n        }\n        \n        unordered_map<int, int> mp;     // ----> will contains frequency of roots of each element\n        int ans = 1;\n        \n        for(int num : nums){\n            int root = ds_find(ds, num);\n            mp[root]++;\n            \n            ans = max(ans, mp[root]);  // ----> Ans will be the max frequency of all roots\n        }\n        \n        return ans;\n    }\n```
[]