1. 문제 설명

도로

2. 문제 분석

MST에 포함된 간선을 확인한다.

3. 나의 풀이

import sys
import heapq

def find(node):
    if parents[node] == node: return node
    else:
        parents[node] = find(parents[node])
        return parents[node]
def union(node1,node2):
    root1, root2 = find(node1), find(node2)
    if root1 == root2: return False
    else:
        parents[root2] = root1
        return True

t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    n, m, p, q = map(int, sys.stdin.readline().rstrip().split())
    parents = [i for i in range(n+1)]
    pq = []
    for _ in range(m):
        a, b, c = map(int, sys.stdin.readline().rstrip().split())
        heapq.heappush(pq, [c, a, b])

    edge_cnt = 0
    is_pq_in = False
    while pq:
        cost, node1, node2 = heapq.heappop(pq)
        if union(node1, node2):
            if (node1 == p and node2 == q) or (node2 == p and node1 ==q):
                is_pq_in = True
                break
            edge_cnt += 1
            if edge_cnt == n-1: break
    if is_pq_in: print("YES")
    else: print("NO")