题解 | #最小生成树#

import sys
import heapq
from typing import List

class Solution:
    def miniSpanningTree(self, n: int, m: int, cost: List[List[int]]) -> int:
        graph = [[] for _ in range(n + 1)]  # 构建邻接表描述的图
        for u, v, c in cost:
            graph[u].append((v, c))
            graph[v].append((u, c))
        
        pq = []  # 优先队列，用于存储边的信息 (c, n)
        heapq.heappush(pq, (0, 1))  # 先将源点 1 和权值 0 加入到优先队列中，根据权值排序，权值最小的边排在队首
        visited = set()  # 记录已访问的结点
        total_cost = 0	
        
        while pq:
            c, n = heapq.heappop(pq)  # 弹出权值最小的边
            if n in visited:
                continue
            visited.add(n)	# 若结点未被访问，添加至访问集合中
            total_cost += c
            for neighbor, edge_cost in graph[n]:
                if neighbor not in visited:#将图中未被访问的边添加到队列中
                    heapq.heappush(pq, (edge_cost, neighbor))
        
        return total_cost