BOJ 13905 세부(Python 3)

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

-크루스칼 알고리즘을 사용함

-재귀함수 깊이를 설정 안해주면 런타임 에러가 나옴

주의할 점은 다른 MST문제와 다르게, 매 탐색마다 출발점이랑 도착점이랑 같은 연합인지 확인해봐야 함

그래야 가져갈 수 있는 최대한의 빼빼로를 출력할 수 있음

코드확인

def F(x):
    if S[x]==x:return x
    S[x]=F(S[x])
    return S[x]
 
import sys
sys.setrecursionlimit(100000)
input=__import__('sys').stdin.readline
n,m=map(int,input().split())
s,e=map(int,input().split())
S=[i for i in range(n+1)]
D=[]
for i in range(m):
    a,b,c=map(int,input().split())
    D.append((c,a,b))
D.sort(reverse=True)
for i in range(m):
    if F(D[i][1])!=F(D[i][2]):
        S[F(D[i][1])]=F(D[i][2])
        if S[e]!=-1 and S[F(e)]==S[F(s)]:
            print(D[i][0])
            exit()
print(0)