【并集查找 最大公约数 调和数】952. 按公因数计算最大组件大小

class CUnionFind
{
public:
  CUnionFind(int iSize) :m_vNodeToRegion(iSize)
  {
    for (int i = 0; i < iSize; i++)
    {
      m_vNodeToRegion[i] = i;
    }
    m_iConnetRegionCount = iSize;
  } 
  CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
  {
    for (int i = 0; i < vNeiBo.size(); i++) {
      for (const auto& n : vNeiBo[i]) {
        Union(i, n);
      }
    }
  }
  int GetConnectRegionIndex(int iNode)
  {
    int& iConnectNO = m_vNodeToRegion[iNode];
    if (iNode == iConnectNO)
    {
      return iNode;
    }
    return iConnectNO = GetConnectRegionIndex(iConnectNO);
  }
  void Union(int iNode1, int iNode2)
  {
    const int iConnectNO1 = GetConnectRegionIndex(iNode1);
    const int iConnectNO2 = GetConnectRegionIndex(iNode2);
    if (iConnectNO1 == iConnectNO2)
    {
      return;
    }
    m_iConnetRegionCount--;
    if (iConnectNO1 > iConnectNO2)
    {
      UnionConnect(iConnectNO1, iConnectNO2);
    }
    else
    {
      UnionConnect(iConnectNO2, iConnectNO1);
    }
  }
  bool IsConnect(int iNode1, int iNode2)
  {
    return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
  }
  int GetConnetRegionCount()const
  {
    return m_iConnetRegionCount;
  }
  vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
  {
    const int iNodeSize = m_vNodeToRegion.size();
    vector<int> vRet(iNodeSize);
    for (int i = 0; i < iNodeSize; i++)
    {
      vRet[GetConnectRegionIndex(i)]++;
    }
    return vRet;
  }
  std::unordered_map<int, vector<int>> GetNodeOfRegion()
  {
    std::unordered_map<int, vector<int>> ret;
    const int iNodeSize = m_vNodeToRegion.size();
    for (int i = 0; i < iNodeSize; i++)
    {
      ret[GetConnectRegionIndex(i)].emplace_back(i);
    }
    return ret;
  }
private:
  void UnionConnect(int iFrom, int iTo)
  {
    m_vNodeToRegion[iFrom] = iTo;
  }
  vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
  int m_iConnetRegionCount;
};
class Solution {
public:
  int largestComponentSize(vector<int>& nums) {
    m_c = nums.size();
    const int iMax = *std::max_element(nums.begin(), nums.end());
    CUnionFind uf(m_c);
    vector<int> vIndex(iMax + 1, -1);
    for (int i = 0; i < m_c; i++) {
      if (-1 == vIndex[nums[i]]) {
        vIndex[nums[i]] = i;
      }
      else
      {
        uf.Union(i, vIndex[nums[i]]);
      }
    }
    for (int x = 2; x <= iMax; x++) {
      int pre = -1;
      for (int cur = x; cur <= iMax; cur += x) {
        if (-1 == vIndex[cur]) { continue; }
        if (-1 == pre) {
          pre = vIndex[cur];
        }
        else {
          uf.Union(pre, vIndex[cur]);
        }
      }
    }
    auto m = uf.GetNodeOfRegion();
    int iRet = 0;
    for (const auto& [tmp, v] : m) {
      iRet = max(iRet, (int)v.size());
    }
    return iRet;
  }
  int m_c;
};

template<class T>
void Assert(const T& t1, const T& t2)
{
    assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
    if (v1.size() != v2.size())
    {
        assert(false);
        return;
    }
    for (int i = 0; i < v1.size(); i++)
    {
        Assert(v1[i], v2[i]);
    }
}
int main()
{
  vector<int> nums;
  {
    Solution sln;
    nums = { 20,50,9,63 };
    auto res = sln.largestComponentSize(nums);
    Assert(2, res);
  }
  {
    Solution sln;
    nums = { 4, 6, 15, 35 };
    auto res = sln.largestComponentSize(nums);
    Assert(4, res);
  }
  
  {
    Solution sln;
    nums = { 2,3,6,7,4,12,21,39 };
    auto res = sln.largestComponentSize(nums);
    Assert(8, res);
  }
}