最大边最小的连通树

方法一：二分+并查集判连通

本方法无需排序，具体步骤如下

1. 首先设置0到10000之间的数作为最长边的上限（这一步写成二分）

2. 写并查集板子，逐步加入所有边，加入条件：1. 边长小于设置的上限 2.两端点根不同

3. 如果所有点能够连通，则进行并查集合并结束后会产生n-1条边，此时二分条件成立

4. 二分搜索直至找到最大边

python版本

#最大边最小的连通树
#二分 + 并查集
class UFS():
    def __init__(self,n):
        self.father = {}
        self.size = {}
        for i in range(1,n+1):
            self.father[i] = i
            self.size[i] = 1

    def findRoot(self,node):
        father = self.father[node]
        if father != node:
            father = self.findRoot(father)
        self.father[node] = father
        return father

    def union(self,node_a,node_b):
        root_a = self.findRoot(node_a)
        root_b = self.findRoot(node_b)

        if root_a != root_b:
            if self.size[root_a] > self.size[root_b]:
                self.father[root_b] = root_a
                self.size[root_a] += seelf.size[root_b]
            else:
                self.father[root_a] = root_b
                self.size[root_b] = self.size[root_a]
            return True
        else:
            return False

def solu(x):
    ufs = UFS(n)
    num = 0
    for i in range(m):
        if data[i][2] > x:
            continue
        if ufs.union(data[i][0],data[i][1]):
            num += 1
    if num != n - 1:
        return float('inf'),False
    else:
        return num,True


n,m = map(int,input().split())

data = []
for i in range(m):
    a,b,c = map(int,input().split())
    data.append((a,b,c))

left = 0
right = 10000
resNum = 0
while left < right:
    mid = left + right >> 1
    num,isok = solu(mid)
    if isok:
        right = mid
        resNum = num
    else:
        left = mid + 1


print(resNum,left)

方法二：裸克鲁斯卡尔

想到这么做必须要很熟悉这个算法的原理

1. 首先所有点连通，且两点用边最多一条，则边数必须为n - 1条

2. 对边长进行排序后，克鲁斯卡尔逐渐加入边，当全部连通后，则最后一条边一定为最长边

python版本

class UFS():
    def __init__(self,n):
        self.father = {}
        self.size = {}
        for i in range(1,n+1):
            self.father[i] = i
            self.size[i] = 1

    def findRoot(self,node):
        father = self.father[node]
        if father != node:
            father = self.findRoot(father)
        self.father[node] = father
        return father

    def union(self,node_a,node_b):
        root_a = self.findRoot(node_a)
        root_b = self.findRoot(node_b)

        if root_a != root_b:
            if self.size[root_a] > self.size[root_b]:
                self.father[root_b] = root_a
                self.size[root_a] += seelf.size[root_b]
            else:
                self.father[root_a] = root_b
                self.size[root_b] = self.size[root_a]
            return True
        else:
            return False

def solu(x):
    ufs = UFS(n)
    num = 0
    for i in range(m):
        if data[i][2] > x:
            continue
        if ufs.union(data[i][0],data[i][1]):
            num += 1
    if num != n - 1:
        return float('inf'),False
    else:
        return num,True


n,m = map(int,input().split())
data = []
ufs = UFS(n)
for i in range(m):
    a,b,c = map(int,input().split())
    data.append((a,b,c))
data = sorted(data,key = lambda x : x[2])


for i in range(m):
    if ufs.union(data[i][0],data[i][1]):
        res = data[i][2]

print(n - 1,res)