Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

सामान्य गुणक द्वारा सबसे बड़ा घटक आकार C++ में

मान लीजिए हमारे पास अद्वितीय धनात्मक पूर्णांकों की एक सरणी 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
  1. - C++ में आकार K के M नॉन-ओवरलैपिंग सबएरे का अधिकतम योग

    समस्या कथन एक ऐरे और दो संख्याएं M और K दी गई हैं। हमें ऐरे में आकार K के अधिकतम M सबएरे का योग ढूंढना है (नॉन-ओवरलैपिंग)। (ऐरे का क्रम अपरिवर्तित रहता है)। K सबएरे का आकार है और M सबएरे की संख्या है। यह माना जा सकता है कि ऐरे का आकार m*k से अधिक है। यदि कुल ऐरे का आकार k का गुणक नहीं है, तो हम आंश

  1. - C++ में ऐरे में सबसे बड़ा d ढूंढें जैसे कि a + b + c = d

    मान लीजिए हमारे पास पूर्णांकों का एक सेट है। हमें एक संख्या d ढूंढनी है, जहां d = a + b + c, और हमें (a + b + c) को अधिकतम करना है, सभी a, b, c, और d सेट में मौजूद हैं। सेट में कम से कम एक एलिमेंट होगा, और अधिकतम 1000 एलिमेंट्स। प्रत्येक एलिमेंट एक परिमित संख्या होगी। यदि सेट {2, 3, 5, 7, 12} है, त

  1. - C++ प्रोग्राम: लॉन्गेस्ट कॉमन सबसीक्वेंस (LCS)

    एक सबसीक्वेंस तत्वों के समूह का वही क्रम वाला अनुक्रम है। अनुक्रम stuv के लिए, सबसीक्वेंस हैं stu, tuv, suv, आदि। लंबाई n के एक स्ट्रिंग के लिए, उस स्ट्रिंग से सबसीक्वेंस बनाने के 2^n तरीके हो सकते हैं। उदाहरण स्ट्रिंग्स ABCDGH और AEDFHR के लिए सबसे लंबी सामान्य सबसीक्वेंस की लंबाई 3 है। #include &l