इस समस्या में, हमें N संख्याओं की एक सरणी arr दी गई है जहां arr[i] (i+1)वें नोड को दर्शाता है। साथ ही, M जोड़े किनारे हैं जहां u और v किनारे से जुड़े नोड्स को दर्शाते हैं। हमारा कार्य एक प्रोग्राम बनाना है जो अविभाजित ग्राफ के सभी संयोजी घटकों में न्यूनतम तत्वों का योग निकाले। यदि एक नोड की किसी अन्य नोड से कोई कनेक्टिविटी नहीं है, तो इसे एक नोड वाले घटक के रूप में गिनें।
आइए एक उदाहरण लेकर समस्या को समझते हैं,
इनपुट
arr[] = {2, 7, 5, 1, 2} m = 2
1 2
4 5
आउटपुट
8
व्याख्या
ऊपर चित्रित ग्राफ नीचे है -

हमारे पास दो संयोजित नोड्स और एक एकल नोड है
तो, आइए सभी संयोजी घटकों का न्यूनतम लें
न्यूनतम (नोड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