Dada una array A de N números donde A i representa el valor del (i+1) Node . También se dan M pares de aristas donde u y v representan los Nodes que están conectados por una arista. La tarea es encontrar la suma del elemento mínimo en todos los componentes conectados del gráfico no dirigido dado. Si un Node no tiene conectividad con ningún otro Node, cuéntelo como un componente con un Node.
Ejemplos:
Entrada: a[] = {1, 6, 2, 7, 3, 8, 4, 9, 5, 10} m = 5
1 2
3 4
5 6
7 8
9 10Salida: 15
Los componentes conectados son: 1–2, 3–4, 5–6, 7–8 y 9–10
Suma del mínimo de todos ellos: 1 + 2 + 3 + 4 + 5 = 15Entrada: a[] = {2, 5, 3, 4, 8} m = 2
1 4
4 5
Salida: 10
Enfoque: encontrar componentes conectados para un gráfico no dirigido es una tarea más fácil. Hacer un BFS o DFS a partir de cada vértice no visitado nos dará nuestros componentes conectados. Cree una array visited[] que inicialmente tenga todos los Nodes marcados como False. Itere todos los Nodes, si el Node no se visita, llame a la función DFS() para que todos los Nodes conectados directa o indirectamente al Node se marquen como visitados. Mientras visita todos los Nodes conectados directa o indirectamente, almacene el valor mínimo de todos los Nodes. Cree una suma variable que almacene la suma del mínimo de todos estos componentes conectados. Una vez visitados todos los Nodes, sumatendrá la respuesta al problema.
A continuación se muestra la implementación del enfoque anterior:
// C++ program to find the sum
// of the minimum elements in all
// connected components of an undirected graph
#include <bits/stdc++.h>
using namespace std;
const int N = 10000;
vector<int> graph[N];
// Initially all nodes
// marked as unvisited
bool visited[N];
// DFS function that visits all
// connected nodes from a given node
void dfs(int node, int a[], int mini)
{
// Stores the minimum
mini = min(mini, a[node]);
// Marks node as visited
visited[node] = true;
// Traversed in all the connected nodes
for (int i : graph[node]) {
if (!visited[i])
dfs(i, a, mini);
}
}
// Function to add the edges
void addedge(int u, int v)
{
graph[u - 1].push_back(v - 1);
graph[v - 1].push_back(u - 1);
}
// Function that returns the sum of all minimums
// of connected componenets of graph
int minimumSumConnectedComponents(int a[], int n)
{
// Initially sum is 0
int sum = 0;
// Traverse for all nodes
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int mini = a[i];
dfs(i, a, mini);
sum += mini;
}
}
// Returns the answer
return sum;
}
// Driver Code
int main()
{
int a[] = {1, 6, 2, 7, 3, 8, 4, 9, 5, 10};
// Add edges
addedge(1, 2);
addedge(3, 4);
addedge(5, 6);
addedge(7, 8);
addedge(9, 10);
int n = sizeof(a) / sizeof(a[0]);
// Calling Function
cout << minimumSumConnectedComponents(a, n);
return 0;
}
15