当前位置:网站首页>LeetCode:952. 按公因数计算最大组件大小【欧拉筛 + 并查集】
LeetCode:952. 按公因数计算最大组件大小【欧拉筛 + 并查集】
2022-07-31 05:49:00 【星空皓月】
题目描述
给定一个由不同正整数的组成的非空数组 nums ,考虑下面的图:
- 有 nums.length 个节点,按从 nums[0] 到 nums[nums.length - 1] 标记;
- 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时,nums[i] 和 nums[j]之间才有一条边。
返回 图中最大连通组件的大小 。
输入与输出
输入:nums = [4,6,15,35]
输出:4
思路
题目将nums[i]和nums[j]找到一个大于一的公因数,即为两个数至少有一个相同的质数。然后将这两个节点连接。找相同质数用欧拉筛,然后将这个顶点的质数与num合并,用并查集来合并,最后遍历数组进行计数。
代码
class Solution {
public:
const static int n = 1e5 + 7;
int primes[n];
int father[n];
int isPrimes[n];
int cnt;
int numer[n];
int find(int x) {
return x == father[x] ? x : father[x] = find(father[x]);
}
void merge(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) {
father[fx] = fy;
}
}
void init() {
for (int i = 1; i < n; ++i) {
father[i] = i;
}
for (int i = 2; i < n; ++i) {
if (isPrimes[i] == 0) {
primes[cnt++] = i;
}
for (int j = 0; i * primes[j] < n; ++j) {
isPrimes[i * primes[j]] = 1;
if (i % primes[j] == 0) {
break;
}
}
}
}
int largestComponentSize(vector<int>& nums) {
init();
for (auto num : nums) {
int tmp = num;
for (int i = 0; i < cnt && primes[i] * primes[i] <= tmp; ++i) {
if (tmp % primes[i] == 0) {
merge(num, primes[i]);
while(tmp % primes[i] == 0) {
tmp /= primes[i];
}
}
}
if(tmp > 1) {
merge(num, tmp);
}
}
int ans = 0;
for (auto num : nums) {
ans = max(ans, ++numer[find(num)]);
}
return ans;
}
};
边栏推荐
猜你喜欢
随机推荐
Exam Questions Previous True Questions Wrong Bills [The Fourth Session] [Provincial Competition] [Group B]
Core Tower Electronics won the championship in the Wuhu Division of the 11th China Innovation and Entrepreneurship Competition
浅层了解欧拉函数
树状数组(单点修改区间查询和区间修改单点查询)
【云原生】-Docker安装部署分布式数据库 OceanBase
外贸网站优化-外贸网站优化教程-外贸网站优化软件
Web浏览器工作流程解析
银河麒麟V10 sp1服务器安装英伟达显卡驱动
MySQL笔记下
How to use repeating-linear-gradient
第三方库-store
js原型详解
试题 历届真题 错误票据【第四届】【省赛】【B组】
零样本学习&Domain-aware Visual Bias Eliminating for Generalized Zero-Shot Learning
银河麒麟服务器v10 sp1安装.net6
Some derivation formulas for machine learning backpropagation
NFS共享存储服务
(border-box) The difference between box model w3c and IE
芯塔电子斩获第十一届中国双创大赛芜湖赛区桂冠
nohup原理