이 문제에서 arr[i]는 (i+1)번째 노드를 나타내는 N개의 숫자 배열 arr이 주어집니다. 또한 u와 v가 에지로 연결된 노드를 나타내는 M 쌍의 에지가 있습니다. 우리의 임무는 무방향 그래프의 연결된 모든 구성 요소에서 최소 요소의 합을 찾는 프로그램을 만드는 것입니다. 노드가 다른 노드와 연결되어 있지 않으면 하나의 노드가 있는 구성 요소로 간주합니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력
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)을 사용하여 무방향 그래프의 연결된 모든 노드를 찾은 다음 이중 방문이 없는 모든 노드에 대해 방문 배열을 만듭니다. 직접 또는 간접적으로 연결된 연결된 노드를 방문하면 모든 연결의 최소값을 찾습니다. 그리고 이 sum 변수의 최소값을 추가합니다. 모든 노드를 방문한 후 합계를 출력합니다.
예시
솔루션의 작동을 설명하는 프로그램,
#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<<"The sum of minimum elements in all connected components of an undirected graph is ";
cout<<minSum(arr, n);
return 0;
} 출력
The sum of minimum elements in all connected components of an undirected graph is 8