952. Largest Component Size by Common Factor

• finding way to add edge in graph, was the most difficult part.
• for that we will store the edges, common factor wise, later make edge b/w all of them.
• for example

  edges: [2, 4, 6, 9, 10]
  index: [0, 1, 2, 3, 4]
  
  mapping common factor to index
  
  2: 0, 1, 2, 4
  3: 2, 3
  5: 4
  7: NA
  

Code implementation

```cpp class UnionFind { public: std::vector Parent; std::vector Size; void init(int n) { Size.resize(int(3e5) + 5, 1); Parent.resize(int(3e5) + 5, 0); for (int i = 0; i < n; i++) Parent[i] = i; } void makeSet(int n) { Parent[n] = n; Size[n] = 1; } int findSet(int i) { return (Parent[i] == i) ? i : (Parent[i] = findSet(Parent[i])); } bool isSameSet(int i, int j) { return findSet(i) == findSet(j); } void unionSet(int a, int b) { a = findSet(a); b = findSet(b); if (a == b) return; if (Size[a] < Size[b]) std::swap(a, b); Parent[b] = a; Size[a] += Size[b]; } }; class Solution { public: int largestComponentSize(vector &nums) { UnionFind dsu; map<int, vi> mp; for (int i = 0; i < nums.size(); i++) { auto temp = factorize(nums[i]); for (const auto &[key, value] : temp) mp[key].push_back(i); } dsu.init(2e5); for (const auto &[key, value] : mp) { for (int i = 0; i < value.size() - 1; i++) { dsu.unionSet(value[i], value[i + 1]); } } return *max_element(all(dsu.Size)); } }; ``` </details>