Tổng phần tử nhỏ nhất các thành phần liên thông trong đồ thị vô hướng trong C++

Cho mảng arr[N] (arr[i] là giá trị nút i+1) và M cặp cạnh. Tìm tổng các giá trị nhỏ nhất của mỗi thành phần liên thông (connected component). Nút đơn lẻ tính là một thành phần.

Ví dụ

Đầu vào: arr[] = {2, 7, 5, 1, 2}, M = 2, cạnh: (1,2), (4,5)

Đầu ra: 8

Giải thích: Thành phần 1: {1,2} min=2. Thành phần 2: {4,5} min=1. Thành phần 3: {3} min=5. Tổng = 2+1+5=8

Phương pháp: DFS

• Xây đồ thị từ danh sách cạnh
• Mảng visited[] đánh dấu nút đã duyệt
• Với mỗi nút chưa duyệt: DFS tìm min trong thành phần, cộng vào tổng

Ví dụ mã nguồn

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

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

void dfs(int u, int arr[], int &minVal) {
    minVal = min(minVal, arr[u]);
    visited[u] = true;
    for (int v : graph[u])
        if (!visited[v]) dfs(v, arr, minVal);
}

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

int tongMinThanhPhan(int arr[], int n) {
    int tong = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            int minVal = arr[i];
            dfs(i, arr, minVal);
            tong += minVal;
        }
    }
    return tong;
}

int main() {
    int arr[] = {2, 7, 5, 1, 3};
    themCanh(1, 2);
    themCanh(4, 5);
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Tổng min các thành phần liên thông: " << tongMinThanhPhan(arr, n);
    return 0;
}

Kết quả

Tổng min các thành phần liên thông: 8