โปรแกรมหาผลรวมค่าต่ำสุดในแต่ละ Connected Component ของ Undirected Graph C++

ภาพรวมปัญหา

กำหนดกราฟ Undirected Graph ที่มี N โหนด (โหนด i มีค่า arr[i-1]) และ M Edge ให้หาผลรวมของค่าต่ำสุด (Minimum Value) ในแต่ละ Connected Component

โหนดที่ไม่มี Edge เชื่อม (Isolated Node) ถือเป็น Component เดียว

ตัวอย่าง

arr = [2, 7, 5, 1, 3]  // Node 1=2, Node 2=7, Node 3=5, Node 4=1, Node 5=3
Edges: (1,2), (4,5)

Components:
- Component 1: Nodes {1,2} → Values {2,7} → Min = 2
- Component 2: Nodes {4,5} → Values {1,3} → Min = 1
- Component 3: Node {3} → Values {5} → Min = 5

Sum = 2 + 1 + 5 = 8

อัลกอริทึม: DFS + Visited Array

1. สร้าง Adjacency List จาก Edge List
2. สร้าง Visited Array ขนาด N
3. สำหรับโหนดทุกตัวที่ยังไม่ Visited:
   • เริ่ม DFS/BFS จากโหนดนั้น
   • หาค่า Minimum ใน Component นี้
   • บวกเข้ากับผลรวม Total
4. คืนค่า Total Sum

ตัวอย่างโค้ด C++ (DFS Recursive)

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

const int MAXN = 100005;
vector graph[MAXN];
bool visited[MAXN];
int values[MAXN];

int dfsMin(int node) {
    visited[node] = true;
    int minVal = values[node];
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            minVal = min(minVal, dfsMin(neighbor));
        }
    }
    return minVal;
}

long long minSumComponents(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            int componentMin = dfsMin(i);
            sum += componentMin;
        }
    }
    return sum;
}

int main() {
    int n = 5;
    // Values (1-indexed)
    values[1] = 2;
    values[2] = 7;
    values[3] = 5;
    values[4] = 1;
    values[5] = 3;
    
    // Edges
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[4].push_back(5);
    graph[5].push_back(4);
    
    cout << "Sum of minimums = " << minSumComponents(n) << endl;  // 8
    
    return 0;
}

ตัวอย่างโค้ด C++ (BFS Iterative - กัน Stack Overflow)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

long long minSumComponentsBFS(int n, vector values, vector>& graph) {
    vector visited(n + 1, false);
    long long sum = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            int minVal = INT_MAX;
            queue q;
            q.push(i);
            visited[i] = true;
            
            while (!q.empty()) {
                int u = q.front(); q.pop();
                minVal = min(minVal, values[u]);
                
                for (int v : graph[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        q.push(v);
                    }
                }
            }
            sum += minVal;
        }
    }
    return sum;
}

int main() {
    int n = 5;
    vector values = {0, 2, 7, 5, 1, 3};  // 1-indexed
    vector> graph(n + 1);
    
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[4].push_back(5);
    graph[5].push_back(4);
    
    cout << "Sum of minimums (BFS) = " << minSumComponentsBFS(n, values, graph) << endl;
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Sum of minimums = 8
Sum of minimums (BFS) = 8

การทำงานขั้นตอน (DFS Trace)

ความซับซ้อนของอัลกอริทึม

• เวลา: O(N + M) - เยี่ยมชมทุกโหนดและ Edge ครั้งเดียว
• พื้นที่: O(N + M) - Adjacency List + Visited Array + Stack/Queue

กรณีทดสอบเพิ่มเติม

// Test 1: Fully Connected
n=4, values={10,20,30,40}, edges={(1,2),(2,3),(3,4),(4,1)}
// 1 Component: min=10, Sum=10

// Test 2: No Edges
n=3, values={5,3,8}, edges={}
// 3 Components: 5+3+8=16

// Test 3: Star Graph
n=5, values={100,1,2,3,4}, edges={(1,2),(1,3),(1,4),(1,5)}
// 1 Component: min=1, Sum=1

// Test 4: Two Separate Triangles
n=6, values={5,3,8, 2,9,1}, edges={(1,2),(2,3),(3,1), (4,5),(5,6),(6,4)}
// Comp1: {1,2,3} min=3, Comp2: {4,5,6} min=1, Sum=4

Union-Find (Disjoint Set Union) Alternative

เหมาะสำหรับ Dynamic Connectivity (Edge เพิ่ม/ลบบ่อย)

class DSU {
    vector parent, minVal;
public:
    DSU(int n, vector& values) : parent(n+1), minVal(n+1) {
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            minVal[i] = values[i];
        }
    }
    
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a != b) {
            parent[b] = a;
            minVal[a] = min(minVal[a], minVal[b]);
        }
    }
    
    long long getSum() {
        long long sum = 0;
        for (int i = 1; i < parent.size(); i++) {
            if (parent[i] == i) sum += minVal[i];
        }
        return sum;
    }
};

ข้อควรระวัง

• Indexing: โจทย์มักใช้ 1-indexed (Node 1..N) แต่อาร์เรย์ C++ ใช้ 0-indexed
• Stack Overflow: DFS Recursive อาจล้มถ้า Component สูงมาก → ใช้ BFS หรือ Iterative DFS
• Multiple Edges/Self-loops: ไม่ส่งผลต่อ Minimum แต่ควร Handle ให้ถูกต้อง
• Large Values: ใช้ long long สำหรับ Sum