문제

https://www.acmicpc.net/problem/27945

풀이

간선을 N-1개만 사용할 수 있다는 점에서 MST를 떠올릴 수 있었다.
크루스칼 알고리즘을 통해 MST를 찾다가 가중치 t가 점프한다면 불연속하게 되므로 멈춰주면 된다.

코드

import sys

input = sys.stdin.readline


def solve():
    n, m = map(int, input().split())
    edges = []
    par = [-1 for _ in range(n+1)]
    day = 1

    def find(cur):
        if par[cur] < 0:
            return cur
        par[cur] = find(par[cur])
        return par[cur]

    def union(u, v):
        u, v = find(u), find(v)
        if u == v:
            return False
        if par[u] < par[v]:
            u, v = v, u
        par[v] += par[u]
        par[u] = v
        return True

    for i in range(m):
        u, v, t = map(int, input().split())
        edges.append([u, v, t])

    # ASC sorting with t's value
    edges = sorted(edges, key=lambda x: x[2])

    for u, v, t in edges:
        if t != day:
            break
        if not union(u, v):
            break
        day += 1

    print(day)


solve()