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

C++ में अविभाजित ग्राफ के सभी संयोजी घटकों में न्यूनतम तत्वों का योग


इस समस्या में, हमें N संख्याओं की एक सरणी arr दी गई है जहां arr[i] (i+1)वें नोड को दर्शाता है। साथ ही, M जोड़े किनारे हैं जहां u और v किनारे से जुड़े नोड्स को दर्शाते हैं। हमारा कार्य एक प्रोग्राम बनाना है जो अविभाजित ग्राफ के सभी संयोजी घटकों में न्यूनतम तत्वों का योग निकाले। यदि एक नोड की किसी अन्य नोड से कोई कनेक्टिविटी नहीं है, तो इसे एक नोड वाले घटक के रूप में गिनें।

आइए एक उदाहरण लेकर समस्या को समझते हैं,

इनपुट

arr[] = {2, 7, 5, 1, 2} m = 2
1 2
4 5

आउटपुट

8

व्याख्या

ऊपर चित्रित ग्राफ नीचे है -

C++ में अविभाजित ग्राफ के सभी संयोजी घटकों में न्यूनतम तत्वों का योग

हमारे पास दो संयोजित नोड्स और एक एकल नोड है

तो, आइए सभी संयोजी घटकों का न्यूनतम लें

न्यूनतम (नोड1 और नोड2) = न्यूनतम (2, 7) = 2

न्यूनतम (नोड4 और नोड5) = न्यूनतम (1, 3) = 1

न्यूनतम (नोड3) = न्यूनतम (5) = 5

योग = 1 + 2 + 5 = 8

इस समस्या को हल करने के लिए, हम किसी भी ट्रैवर्सल तकनीक (BFS या DFS) का उपयोग करके अविभाजित ग्राफ के सभी संयोजित नोड्स को ढूंढेंगे और फिर सभी नोड्स के लिए एक विज़िटेड सरणी बनाएंगे जो उस घटक के लिए देखे गए हैं ताकि कोई डबल विज़िट न हो। संयोजित नोड्स पर जाकर जो सीधे या परोक्ष रूप से जुड़े हुए हैं, हम सभी कनेक्शन्स का न्यूनतम ढूंढेंगे। और इस घटक के न्यूनतम मान को योग चर में जोड़ेंगे। सभी नोड्स को देखने के बाद, हम योग प्रिंट करेंगे।

उदाहरण

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

#include <bits/stdc++.h>
using namespace std;

const int N = 100;
vector<int> graph[N];
bool visited[N];

void dfs(int node, int arr[], int &minimum) {
    minimum = min(minimum, arr[node]);
    visited[node] = true;
    for (int i : graph[node]) {
        if (!visited[i])
            dfs(i, arr, minimum);
    }
}

void createEdge(int u, int v) {
    graph[u - 1].push_back(v - 1);
    graph[v - 1].push_back(u - 1);
}

int minSum(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            int minimum = arr[i];
            dfs(i, arr, minimum);
            sum += minimum;
        }
    }
    return sum;
}

int main() {
    int arr[] = {2, 7, 5, 1, 3};
    createEdge(1, 2);
    createEdge(4, 5);
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "अविभाजित ग्राफ के सभी संयोजी घटकों में न्यूनतम तत्वों का योग है ";
    cout << minSum(arr, n);
    return 0;
}

आउटपुट

अविभाजित ग्राफ के सभी संयोजी घटकों में न्यूनतम तत्वों का योग है 8

  1. C++ में ट्री में सभी नोड्स तक जानकारी पास करने के लिए न्यूनतम पुनरावृत्तियों की संख्या C++ में ट्री में सभी नोड्स तक जानकारी पास करने के लिए न्यूनतम पुनरावृत्तियों की संख्या

    हमें n संख्या में नोड्स के साथ एक ट्री डेटा संरचना दी गई है। दिया गया ट्री एक रूट नोड और संबंधित चाइल्ड्स होगा जो किसी भी संख्या में हो सकते हैं और आगे चाइल्ड के किसी भी संख्या में चाइल्ड हो सकते हैं। कार्य ट्री के रूट नोड द्वारा ट्री में सभी नोड्स तक जानकारी पास करने के लिए आवश्यक न्यूनतम पुनरावृत्

  1. C++ में अप्रत्यक्ष ग्राफ (Undirected Graph) में सभी चक्र (Cycles) प्रिंट करें C++ में अप्रत्यक्ष ग्राफ (Undirected Graph) में सभी चक्र (Cycles) प्रिंट करें

    इस समस्या में, हमें एक अप्रत्यक्ष ग्राफ दिया गया है और हमें ग्राफ में बने सभी चक्रों को प्रिंट करना है। अप्रत्यक्ष ग्राफ एक ग्राफ है जो एक साथ जुड़ा हुआ है। अप्रत्यक्ष ग्राफ के सभी किनारे द्विदिशात्मक हैं। इसे अप्रत्यक्ष नेटवर्क के रूप में भी जाना जाता है। चक्र ग्राफ डेटा संरचना में एक ग्राफ है जिसम

  1. C++ में अविकलित ग्राफ में सभी चक्रों की लंबाई का गुणनफल C++ में अविकलित ग्राफ में सभी चक्रों की लंबाई का गुणनफल

    हमें इनपुट के रूप में अविकलित और अवेटेड ग्राफ दिया गया है और कार्य दिए गए ग्राफ में बने चक्रों का गुणनफल खोजना और परिणाम प्रदर्शित करना है।उदाहरणइनपुटदिए गए आंकड़े में, 8 नोड्स हैं और उनमें से 5 नोड्स 1, 6, 3, 5, 8 सहित चक्र बना रहे हैं और बाकी नोड्स चक्र में शामिल नहीं हैं। तो, चक्र की लंबाई 5 है क