本文涉及知识点
调和级数 并集查找（并差集)
LeetCode1627. 带阈值的图连通性
有 n 座城市，编号从 1 到 n 。编号为 x 和 y 的两座城市直接连通的前提是： x 和 y 的公因数中，至少有一个 严格大于 某个阈值 threshold 。更正式地说，如果存在整数 z ，且满足以下所有条件，则编号 x 和 y 的城市之间有一条道路：
x % z == 0
y % z == 0
z > threshold
给你两个整数 n 和 threshold ，以及一个待查询数组，请你判断每个查询 queries[i] = [ai, bi] 指向的城市 ai 和 bi 是否连通（即，它们之间是否存在一条路径）。
返回数组 answer ，其中answer.length == queries.length 。如果第 i 个查询中指向的城市 ai 和 bi 连通，则 answer[i] 为 true ；如果不连通，则 answer[i] 为 false 。
示例 1：
输入：n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]
输出：[false,false,true]
解释：每个数的因数如下：
1: 1
2: 1, 2
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6
所有大于阈值的的因数已经加粗标识，只有城市 3 和 6 共享公约数 3 ，因此结果是：
[1,4] 1 与 4 不连通
[2,5] 2 与 5 不连通
[3,6] 3 与 6 连通，存在路径 3–6
示例 2：
输入：n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]
输出：[true,true,true,true,true]
解释：每个数的因数与上一个例子相同。但是，由于阈值为 0 ，所有的因数都大于阈值。因为所有的数字共享公因数 1 ，所以所有的城市都互相连通。
示例 3：
输入：n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]]
输出：[false,false,false,false,false]
解释：只有城市 2 和 4 共享的公约数 2 严格大于阈值 1 ，所以只有这两座城市是连通的。
注意，同一对节点 [x, y] 可以有多个查询，并且查询 [x，y] 等同于查询 [y，x] 。
提示：
2 <= n <= 104
0 <= threshold <= n
1 <= queries.length <= 105
queries[i].length == 2
1 <= ai, bi <= cities
ai != bi
调和级数
枚举z，如果符合则通过并集查找连通。
z为1时，需要枚举 n次。
z为2时，需要枚举
n
×
1
2
n \times \frac{1}{2}
n×21
z为3时，需要枚举
n
×
1
3
n \times \frac{1}{3}
n×31
⋮
\vdots
⋮
故时间复杂度是O(nlogn)，其中logn是调和级数之和。
代码
核心代码
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;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
测试用例
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);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
QQ群名片
评论记录：
回复评论：