LeetCode·Daily Question·952. Calculate Maximum Component Size by Common Factor·Union Check

Title

Example

Thoughts

Idea:
Elements are connected to each other by a common factor between them.

1. And search:

There is no need to merge by collection size when building, it can be merged directly.The largest connected component can be found by traversing the union search set once.
Works with path compression.See find function.
2. Common factor:

Note that i * i <= num in the loop, if the data range is larger, it may overflow.Better to use i <= num / i .

For example:
nums = [4 , 6 , 12, 15]
where the factor of each number num in nums greater than 2 is:
4 -> 2
6 -> 2, 3
12 -> 2, 3, 4, 6
15 -> 3, 5
When creating and checking the set, the factor 2 can be used to convert 4, 6, 12 are connected.
6, 12, 15 can be connected by a factor of 3.
And factor 2 and factor 3 are also connected (eg 2 is the parent of 3).
Then the four numbers in the original array are connected.It has the same parent node in the union.

Solve
Finally, the array is traversed once, if its parent node is the same, it is in the same connected component.
Just update the maximum number of occurrences of each parent node.

Code

#define MAX(a, b) ((a) > (b) ? (a) : (b))typedef struct UnionFind {int *parent;int *rank;} UnionFind;UnionFind* unionFindCreate(int n) {UnionFind *obj = (UnionFind *)malloc(sizeof(UnionFind));obj->parent = (int *)malloc(sizeof(int) * n);obj->rank = (int *)malloc(sizeof(int) * n);memset(obj->rank, 0, sizeof(int) * n);for (int i = 0; i < n; i++) {obj->parent[i] = i;}return obj;}int find(const UnionFind *obj, int x) {if (obj->parent[x] != x) {obj->parent[x] = find(obj, obj->parent[x]);}return obj->parent[x];}void uni(UnionFind *obj, int x, int y) {int rootx = find(obj, x);int rooty = find(obj, y);if (rootx != rooty) {if (obj->rank[rootx] > obj->rank[rooty]) {obj->parent[rooty] = rootx;} else if (obj->rank[rootx] < obj->rank[rooty]) {obj->parent[rootx] = rooty;} else {obj->parent[rooty] = rootx;obj->rank[rootx]++;}}}void unionFindFree(UnionFind *obj) {free(obj->parent);free(obj->rank);free(obj);}int largestComponentSize(int* nums, int numsSize) {int m = nums[0];for (int i = 0; i < numsSize; i++) {m = MAX(m, nums[i]);}UnionFind *uf = unionFindCreate(m + 1);for (int i = 0; i < numsSize; i++) {int num = nums[i];for (int i = 2; i * i <= num; i++) {if (num % i == 0) {uni(uf, num, i);uni(uf, num, num / i);}}}int *counts = (int *)malloc(sizeof(int) * (m + 1));memset(counts, 0, sizeof(int) * (m + 1));int ans = 0;for (int i = 0; i < numsSize; i++) {int root = find(uf, nums[i]);counts[root]++;ans = MAX(ans, counts[root]);}free(counts);unionFindFree(uf);return ans;}

Time and space complexity