題目背景

A地區(qū)在地震過(guò)后，連接所有村莊的公路都造成了損壞而無(wú)法通車。政府派人修復(fù)這些公路。

題目描述

給出A地區(qū)的村莊數(shù)，公路是雙向的。并告訴你每條公路的連著哪兩個(gè)村莊，并告訴你什么時(shí)候能修完這條公路。問(wèn)最早什么時(shí)候任意兩個(gè)村莊能夠通車，即最早什么時(shí)候任意兩條村莊都存在至少一條修復(fù)完成的道路（可以由多條公路連成一條道路）

輸入輸出格式

輸入格式：

第1行兩個(gè)正整數(shù)N,M

下面M行，每行3個(gè)正整數(shù)x, y, t，告訴你這條公路連著x,y兩個(gè)村莊，在時(shí)間t時(shí)能修復(fù)完成這條公路。

輸出格式：

如果全部公路修復(fù)完畢仍然存在兩個(gè)村莊無(wú)法通車，則輸出-1，否則輸出最早什么時(shí)候任意兩個(gè)村莊能夠通車。

輸入輸出樣例

輸入樣例#1：

4 4
1 2 6
1 3 4
1 4 5
4 2 3

輸出樣例#1：

5

說(shuō)明

N≤1000,M≤100000
x≤N,y≤N,t≤100000

C++題解可以見(jiàn)我的博客園博文：https://www.cnblogs.com/Weixu-Liu/p/10651745.html

在這個(gè)題中，我用的是python3，注意最后在判斷是否構(gòu)成最小生成樹(shù)的時(shí)候，注意輸入的點(diǎn)的個(gè)數(shù)是否最后遞減到1，如果是，輸出時(shí)間，如果不是，輸出-1。

python3代碼：

n, m = map(int, input().split())
father, edge, ans = [i for i in range(n + 1)], [], -1

def find(x):
    while x != father[x]:
        father[x] = find(father[x])
        x = father[x]
    return x

def merge(a, b):
    ax = find(a)
    bx = find(b)
    if ax == bx: return 0
    else:
        father[ax] = bx
        return 1
for i in range(m):
    u, v, w = map(int, input().split())
    edge.append((u, v, w))
edge.sort(key=lambda e : e[2])
for e in edge:
    if merge(e[0], e[1]) == 1:
        # ans += e[2]
        ans = e[2]
        n -= 1
if n == 1:
    print(ans)
else:
    print(-1)