题解 | #最小生成树#

#一定要注意，去掉指向自身节点的边，被坑了一天

#

class Solution:

def miniSpanningTree(self , n: int, m: int, cost: List[List[int]]) -> int:

# write code here

if n == 1:

return 0

if m == 1:

return cost[0][2]

cost.sort(key = lambda x: x[2])

# 维护一个节点集合hadlink，把第一个边放进去，染色为1号。定义最终返回的结果为mincost，并加入第一个边的cost

# 遍历每个边

# 对于两个节点都不在hadlink里的，染色为其他色号（递增），消费加入mincost

# 对于仅一个节点在hadlink里的，将未在hadlink里的节点染色为边中另一个节点的颜色，消费加入mincost

# 对于两个边不在同一个色号下的，消费加入mincost，把边中色号大的节点赋予色号小的节点，遍历hadlink，把该大色号全部赋予小色号

nodeColorDict = dict()

colorNodeDict = dict()

colorid = 1

minCost = 0

for link in cost:

start = link[0]

end = link[1]

ccost = link[2]

if start == end:

continue

if start not in nodeColorDict.keys() and end not in nodeColorDict.keys():

if colorid not in colorNodeDict:

colorNodeDict[colorid] = set()

colorNodeDict[colorid].add(start)

colorNodeDict[colorid].add(end)

nodeColorDict[start] = colorid

nodeColorDict[end] = colorid

minCost += ccost

colorid += 1

elif start not in nodeColorDict.keys():

colorNodeDict[nodeColorDict[end]].add(start)

nodeColorDict[start] = nodeColorDict[end]

minCost += ccost

# print(ccost)

elif end not in nodeColorDict.keys():

colorNodeDict[nodeColorDict[start]].add(end)

nodeColorDict[end] = nodeColorDict[start]

minCost += ccost

# print(ccost)

elif nodeColorDict[start] != nodeColorDict[end]:

mincolor = min(nodeColorDict[start], nodeColorDict[end])

maxcolor = max(nodeColorDict[start], nodeColorDict[end])

for node in colorNodeDict[maxcolor]:

nodeColorDict[node] = mincolor

colorNodeDict[mincolor].add(node)

colorNodeDict[maxcolor] = set()

minCost += ccost

return minCost