[파이썬] [그래프] 백준 16202 MST 게임

문제

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

16202번: MST 게임

코드

n,m,k=map(int, input().split())

graph=[]
parent=[]
for i in range(n+1):
    parent.append(i)

for i in range(1,m+1):
    a,b=map(int, input().split())
    graph.append([a,b,i])

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

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

graph.sort(key= lambda x: x[2])

flag=False
for i in range(k):
    parent.clear()
    if i>=1:
        graph.pop(0)
    for j in range(n + 1):
        parent.append(j)
    if flag==True:
        print(0, end=" ")
        continue
    mstValue=0
    for a,b,value in graph:
        if find(a)!=find(b):
            union(a,b)
            mstValue+=value
    check = set()
    #mst가 됐는지 확인할때 find() 돌린걸로 확인해야함
    for j in range(1, n + 1):
        if find(j) not in check:
            check.add(find(j))
    if len(check)!=1:
        flag=True
        print(0, end=" ")
        continue
    else:
        print(mstValue, end=" ")

어려웠던점

마지막에 mst가 됐는지 확인할때 find()를 다시 돌려 확인해야 된다는 것을 잊어 해결하는데 시간이 오래 걸렸다.