[슬슬 가지를 먹지 않으면 죽는다/G3/Python3]

27945번 슬슬 가지를 먹지 않으면 죽는다 G3

 

문제
키위새는 가지와 사랑에 빠지면서 가지로 맛있는 요리를 하기 위해 1번부터 N번까지의 번호가 붙은 N개의 요리 학원에 다니기 시작했다. 각 요리 학원 사이에는 총 M개의 양방향 길이 있고, i번째 길에는 정확히 ti일에만 문을 여는 가지 디저트 노점이 있다. (ti는 모두 다르다.) 아직 가지 요리를 배우는 중인 키위새는 직접 가지 요리를 해 먹지는 못하다 보니 가지 부족증(hypomelitzemia)이 발생했다. 키위새는 이제 매일 노점에 들러 가지 디저트를 먹지 않으면 쓰러지게 된다. 심지어 기억력도 퇴화해 N−1개의 길만을 기억할 수 있게 되었다! 모든 요리 학원에 다닐 수 있도록 N−1개의 길을 골랐을 때, 키위새가 쓰러지는 날이 d일차라고 하자. 날짜가 1일 차부터 시작할 때, d의 최댓값을 구해보자.

입력
첫째 줄에 요리 학원의 수 N, 길의 수 M이 주어진다. (2≤N≤1^05; N−1≤M≤min(5×10^5,(N/2))) 둘째 줄부터 M개 줄에 각 길이 연결하는 두 학원의 번호 ui, vi, 길에 있는 노점이 여는 날 ti가 주어진다. (1≤ui, vi≤N; ui≠vi; 1≤ti≤10^9; ti≠tj)  각 요리 학원에서 길을 따라 모든 요리 학원으로 가는 방법이 존재하는 경우만 주어진다. 두 요리 학원 사이를 곧바로 잇는 길은 많아야 하나이다.

출력
첫째 줄에 d의 최댓값을 출력한다.

 

 

자료 구조, 그래프 이론, 그리디 알고리즘, 분리 집합, 최소 스패닝 트리

 

최소 스패닝 트리의 기준이 노점이 열리는 날이라는 점이 조금 특이한 문제였다.

노점을 매일 방문해야 하기 때문에 1일 차부터 순서대로 방문해야 한다.

n-1개의 도로를 선택하기 때문에 이미 연결된 정점 사이에는 더 이상의 간선을 연결하면 안 된다.

 

 

노점이 열리는 날짜를 기준으로 오름차순으로 정렬해야 한다.

그 후 분리 집합을 이용하여 구성하는 방식으로 문제를 풀이할 수 있다.

 

 

import sys

n, m = map(int, sys.stdin.readline().split())
p = [i for i in range(n+1)]

def find(v):
    if p[v] == v: return v
    p[v] = find(p[v])
    return p[v]

def union(v1, v2):
    r1, r2 = find(v1), find(v2)
    p[r1] = r2


lines = []
for _ in range(m):
    v1, v2, c = map(int, sys.stdin.readline().split())
    lines.append((c, v1, v2))

lines.sort()

cur_d = 1
for c, v1, v2 in lines:
    if c != cur_d:
        print(cur_d)
        break
    if find(v1) == find(v2): continue
    union(v1, v2)
    cur_d += 1
else:
    print(cur_d)