当前位置:网站首页>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;
}
};
边栏推荐
猜你喜欢
自动翻译软件-批量批量自动翻译软件推荐
服务器和客户端信息的获取
Some derivation formulas for machine learning backpropagation
引导过程和服务控制
Foreign trade website optimization - foreign trade website optimization tutorial - foreign trade website optimization software
科普 | “大姨太”ETH 和 “小姨太”ETC的爱恨情仇
Shell编程规范与变量
LeetCode brush # 376 # Medium - swing sequence
单点登录 思维导图
浅析重复线性渐变repeating-linear-gradient如何使用
随机推荐
One of the small practical projects - food alliance ordering system
机器学习反向传播的一些推导公式
【并发编程】ReentrantLock的lock()方法源码分析
nohup principle
Redux state management
浅层了解欧拉函数
一文读懂 MongoDB 和 MySQL 的差异
How to choose a suitable UI component library in uni-app
Core Tower Electronics won the championship in the Wuhu Division of the 11th China Innovation and Entrepreneurship Competition
科普 | “大姨太”ETH 和 “小姨太”ETC的爱恨情仇
运行 npm 会弹出询问 “你要如何打开这个文件?“
ls的用法
高并发与多线程之间的难点对比(容易混淆)
文本三剑客之e`grep,seq文本编辑工具
tidyverse笔记——管道函数
《白帽子说Web安全》思维导图
LeetCode brush # 376 # Medium - swing sequence
DDL+DML+DQL
常用命令讲解
Obtaining server and client information