Сумма минимальных элементов во всех компонентах связности неориентированного графа

Опубликовано: 16 Января, 2022

Дан массив A из N чисел, где A _i представляет значение (i + 1) ^-го узла. Также даны M пар ребер, где u и v представляют узлы, соединенные ребром. Задача состоит в том, чтобы найти сумму минимального элемента во всех компонентах связности данного неориентированного графа. Если у узла нет связи с каким-либо другим узлом, считайте его компонентом с одним узлом.

Примеры:

Input: a[] = {1, 6, 2, 7, 3, 8, 4, 9, 5, 10} m = 5
1 2
3 4
5 6
7 8
9 10
Output: 15
Connected components are: 1–2, 3–4, 5–6, 7–8 and 9–10
Sum of Minimum of all them : 1 + 2 + 3 + 4 + 5 = 15
Input: a[] = {2, 5, 3, 4, 8} m = 2
1 4
4 5
Output: 10

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: поиск связанных компонентов для неориентированного графа - более простая задача. Выполнение BFS или DFS, начиная с каждой непосещенной вершины, даст нам наши связанные компоненты. Создайте массив visit [], в котором изначально все узлы помечены как False. Выполните итерацию всех узлов, если узел не посещен, вызовите функцию DFS (), чтобы все узлы, прямо или косвенно подключенные к узлу, были помечены как посещенные. При посещении всех узлов, напрямую или косвенно связанных, сохраните минимальное значение всех узлов. Создайте переменную сумму, в которой хранится сумма минимума всех этих связанных компонентов. Как только все узлы будут посещены, у sum будет ответ на проблему.

Below is the implementation of the above approach:

// 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;
}

Output:

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы Структуры данных

Сумма минимальных элементов во всех компонентах связности неориентированного графа

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

РЕКОМЕНДУЕМЫЕ СТАТЬИ