task2.py

# O(ElogE)
# zawsze s == 0, t == 1

from checker import check
from collections import deque

def edges_to_list(E):
    n = 0

    for u, v, _ in E:
        u -= 1 # korekcja indeksowania od 1
        v -= 1
        if u > n: n = u
        if v > n: n = v

    n += 1

    G = [[] for _ in range(n)]

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

    return G, n

def BFS(G, s, t, n, tmp_weight):
    visited = [False] * n
    Q = deque()

    visited[s] = True
    Q.append(s)

    while len(Q) > 0:
        u = Q.popleft()
        for v, w in G[u]:
            if not visited[v] and w >= tmp_weight: # tmp_weight - wybrana waga, którą staramy się zwiększać
                visited[v] = True
                Q.append(v)

    return visited[t]

def binary_find_weight(G, n, E, s, t):
    p, r = 0, len(E) - 1
    last = 0

    while p < r:
        q = (p + r) // 2
        w = E[q][2]
        
        if BFS(G, s, t, n, w):
            last = q
            p = q + 1
        else:
            r = q - 1

    return E[last][2]


def solution(E):
    s, t = 0, 1
    G, n = edges_to_list(E)

    sorted_E = sorted(E, key = lambda x:x[2])

    return binary_find_weight(G, n, sorted_E, s, t)


check(solution)