【调和级数 并集查找】1627. 带阈值的图连通性

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:
  vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
    CUnionFind uf(n+1);
    for (int z = threshold+ 1; z <= n; z++) {
      for (int i = 2; i * z <= n; i++) {
        uf.Union(z , i * z );
      }
    }
    vector<bool> vRes;
    for (const auto& v : queries) {
      vRes.emplace_back(uf.IsConnect(v[0], v[1]));
    }
    return vRes;
  }
};

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]);
  }
}
template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
int main()
{
  int n,  threshold;
  vector<vector<int>> queries;  
  {
    Solution slu;
    n = 6, threshold = 2, queries = { {1,4},{2,5},{3,6} };
    auto res = slu.areConnected(n, threshold, queries);
    Assert({ false,false,true }, res);
  }
  {
    Solution slu;
    n = 6, threshold = 0, queries = { {4,5},{3,4},{3,2},{2,6},{1,3} };
    auto res = slu.areConnected(n, threshold, queries);
    Assert({ true,true,true,true,true }, res);
  }
  {
    Solution slu;
    n = 5, threshold = 1, queries = { {4,5},{4,5},{3,2},{2,3},{3,4} };
    auto res = slu.areConnected(n, threshold, queries);
    Assert({ false,false,false,false,false }, res);
  }
}