[Leetcode] 952. Largest Component Size by Common Factor

문제 : https://leetcode.com/problems/largest-component-size-by-common-factor/

---

고유한 양의 정수 배열 nums가 주어진다. nums[i], nums[j] (i != j)는 1보다 큰 공약수를 공유할 때서로의 노드는 연결되어있다. 그래프에서 가장 큰 연결 컴포넌트의 크기를 구하라.

---

동일한 약수를 가지는 노드를 연결해야 한다. -> Union-Find 를 사용하자.

nums 배열 중 가장 큰 정수를 구한 뒤 그 크기만큼의 부모 배열을 만든다.

nums 배열을 차례대로 탐색(let, num)하면서 1보다 큰 약수를 구해야하므로 2부터 탐색중인 정수의 루트까지(let, i) 2중 for 문으로 탐색한다.

만일 num이 i로 나누어떨어진다면 i와 num/i 가 num의 약수가 될 수 있으므로 union 함수로 num과 i, num과 num/i의 부모를 연결해준다.

위 방법으로 부모 배열의 갱신을 마쳤다면 nums 배열의 정수들 중 동일한 부모 값을 가지는 요소들의 수를 센 다음 이들 중 가장 큰 값이 정답이 된다.

 

시간복잡도는 배열크기를 N, 요소들의 최대값을 M이라 할 때, Union 함수를 실행하는 로직에서 드는 시간인 O(NlogM).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/952.%20Largest%20Component%20Size%20by%20Common%20Factor.cpp