task1.py

# zawsze s == 0, t == 1
# realnie jest to realizajca maksymalnego drzewa rozpinającego przy pomocy Kruskala

# O(ElogE)

from checker import check

def fix_E(E):
    A = []
    for u, v, w in E:
        A.append((u - 1, v - 1, w))

    return A


def kruskal_mod(E, n, s, t):
    p = [i for i in range(n)] # parents
    r = [0] * n # rank

    E.sort(key = lambda x:x[2], reverse = True)

    def find(x): # szuka wierzchołka drzewa
        if p[x] != x:
            p[x] = find(p[x])

        return p[x]
    
    def union(x, y):
        x = find(x)
        y = find(y)

        if x == y: return
        if r[x] > r[y]:
            p[y] = x
        else:
            p[x] = y
            if r[x] == r[y]:
                r[y] += 1

    for u, v, w in E:
        if find(u) != find(v):
            union(u, v)
            if find(s) == find(t): # jeżeli s i t są w tym samym union, to znaczy, że już zostały połączone ścieżką o maksymalnym minimum
                return w

def solution(E):
    s, t = 0, 1
    E = fix_E(E)

    n = 0 # liczba wirzchołków
    for u, v, _ in E:
        if u > n: n = u
        if v > n: n = v

    n += 1

    return(kruskal_mod(E, n, s, t))


check(solution)