도로 (백준 9344)

MST를 형성하면 되는데 특정 간선이 MST 형성에 필요한 지 확인만 해보는 문제이다. 

크루스칼로 간선들을 확인하면서 미리 입력 받았던 간선이 쓰이는 지 체크한다. 

 

import sys 
import heapq 
input = sys.stdin.readline 
test = int(input())

def find(a):
    if a != parent[a]:
        parent[a] = find(parent[a])
    return parent[a]

def union(a,b):
    a =find(a)
    b =find(b)
    if a <b :
        parent[b] = a 
    else :
        parent[a]= b 
    
    

for _ in range(test):
    n,m,p,q =map(int, input().split())
    parent =[k for k in range(n+1)]
    qq= []
    ans =0 
    flag = 0 
    heapq.heapify(qq)
    
    for i in range(m):
        a,b,c =map(int, input().split())
        heapq.heappush(qq, (c,a,b))
    for i in range(m):
        cost ,x,y= heapq.heappop(qq)
        if find(x)!= find(y):
            ans += cost 
            union(x,y)
            if (x,y) == (p,q) or( x,y) == (p,q) :
                print("YES")
                flag = 1 
    if flag ==0 :
        print("NO")