मान लीजिए हमारे पास अद्वितीय धनात्मक पूर्णांकों की एक सरणी A है, अब निम्नलिखित ग्राफ पर विचार करें: A की लंबाई के नोड्स हैं, लेबल A[0] से A[आकार-1] तक। A[i] और A[j] के बीच एक एज है जब A[i] और A[j] में 1 से बड़ा एक सामान्य गुणक होता है। हमें ग्राफ में सबसे बड़े कनेक्टेड घटक का आकार ढूंढना है।
उदाहरण के लिए, यदि इनपुट [4,6,15,35] है, तो आउटपुट 4 होगा।
हल करने का दृष्टिकोण
हम संख्याओं को उनके अभाज्य गुणनखंडों के माध्यम से जोड़ने के लिए यूनियन-फाइंड (डिसजॉइंट सेट यूनियन) का उपयोग करते हैं:
पथ संपीड़न के साथ पैरेंट और रैंक सरणी इनिशियलाइज़ करें
प्रत्येक संख्या के लिए, उसके सभी अभाज्य गुणनखंड ढूंढें
प्रत्येक अभाज्य गुणनखंड के लिए, इस गुणनखंड वाली पिछली संख्या के साथ यूनियन करें
संख्या को स्वयं एक गुणनखंड के रूप में भी मानें
सबसे बड़े घटक आकार को ट्रैक करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> parent;
vector<int> rank;
int getParent(int x){
if (parent[x] == -1) return x;
return parent[x] = getParent(parent[x]);
}
void unionn(int x, int y){
int parX = getParent(x);
int parY = getParent(y);
if (parX == parY) return;
if (rank[parX] >= rank[parY]) {
rank[parX] += rank[parY];
parent[parY] = parX;
} else {
rank[parY] += rank[parX];
parent[parX] = parY;
}
}
int largestComponentSize(vector<int>& A) {
int ret = 0;
int n = A.size();
parent = vector<int>(n, -1);
rank = vector<int>(n, 1);
unordered_map<int, int> m;
for (int i = 0; i < n; i++) {
int x = A[i];
for (int j = 2; j * j <= x; j++) {
if (x % j == 0) {
if (m.count(j)) unionn(m[j], i);
else m[j] = i;
if (m.count(x / j)) unionn(m[x / j], i);
else m[x / j] = i;
}
}
if (m.count(x)) unionn(m[x], i);
else m[x] = i;
ret = max(ret, rank[getParent(i)]);
}
return ret;
}
};
int main(){
Solution ob;
vector<int> v = {4,6,15,35};
cout << (ob.largestComponentSize(v));
return 0;
}
इनपुट
{4,6,15,35}
आउटपुट
4