Connecting Cities With Minimum Cost: เชื่อมเมืองด้วยต้นทุนต่ำสุด (MST)

โจทย์

มี N เมือง (1..N) และ connections [city1, city2, cost] หา Minimum Spanning Tree (MST) cost เพื่อเชื่อมเมืองทั้งหมด ถ้าไม่ได้ → -1

ตัวอย่าง: N=3, connections=[[1,2,5],[1,3,6],[2,3,1]] → MST = edges (2,3) และ (1,2) cost = 1+5=6 แต่ output ในตัวอย่างคือ -1 (อาจมีข้อผิดพลาดในตัวอย่างต้นฉบับ)

อัลกอริทึม: Kruskal's Algorithm + Union-Find (DSU)

1. เรียง edges ตาม cost น้อยไปมาก
2. Union-Find (Disjoint Set Union) ตรวจสอบ cycle
3. Greedy: เลือก edge ที่ cheap ที่สุดที่ไม่ทำ cycle
4. หยุดเมื่อเลือกได้ N-1 edges (connected)

การติดตั้ง (Python Implementation)

class Solution:
    def minimumCost(self, n: int, connections: list[list[int]]) -> int:
        # Union-Find (DSU)
        parent = list(range(n + 1))
        rank = [0] * (n + 1)
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])  # Path compression
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return False
            # Union by rank
            if rank[px] < rank[py]:
                parent[px] = py
            elif rank[px] > rank[py]:
                parent[py] = px
            else:
                parent[py] = px
                rank[px] += 1
            return True
        
        # Kruskal
        connections.sort(key=lambda x: x[2])  # sort by cost
        total_cost = 0
        edges_used = 0
        
        for u, v, cost in connections:
            if union(u, v):
                total_cost += cost
                edges_used += 1
                if edges_used == n - 1:
                    break
        
        return total_cost if edges_used == n - 1 else -1

# ทดสอบ
ob = Solution()
print(ob.minimumCost(3, [[1,2,5], [1,3,6], [2,3,1]]))  # 6 (ไม่ใช่ -1 ตามโจทย์ต้นฉบับ)
print(ob.minimumCost(4, [[1,2,3],[3,4,4]]))             # -1 (disconnected)

Output

6
-1

แก้ไขตัวอย่างต้นฉบับ

ตัวอย่างในโจทย์เดิมให้ output -1 แต่จริงๆ แล้ว N=3 connections ครบ 3 edges สามารถเชื่อมได้ทั้งหมด MST cost = 6 (เลือก edge cost 1 และ 5) อาจเป็นข้อผิดพลาดในตัวอย่าง

Complexity

• Time: O(E log E) สำหรับ sort + O(E α(N)) สำหรับ Union-Find (α = inverse Ackermann ~ O(1))
• Space: O(N) สำหรับ parent/rank arrays

Alternative: Prim's Algorithm

เหมาะสำหรับ dense graph (E ≈ V²) ใช้ Priority Queue

import heapq

def minimumCost_prim(n, connections):
    adj = [[] for _ in range(n+1)]
    for u, v, w in connections:
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    visited = [False] * (n+1)
    min_heap = [(0, 1)]  # (cost, node)
    total = 0
    count = 0
    
    while min_heap and count < n:
        cost, u = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        total += cost
        count += 1
        for v, w in adj[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (w, v))
    
    return total if count == n else -1

สรุป

Minimum Spanning Tree (MST) เป็นโจทย์คลาสสิก ใช้ Kruskal (sparse graph) หรือ Prim (dense graph) พร้อม Union-Find สำหรับ cycle detection

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ