글 읽기 - Union-Find로 구현했는데 어떤 부분에서 틀리는지 모르겠습니다

dashadower 1년 전 2

Union-find를 바로 구현해면 쉽게 풀리는 문제로 알고있는데 어떤 부분에서 잘못된건지 못찾겠습니다 ㅠㅠ.

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

parent = [x for x in range(n)]

def find(x):
    if x == parent[x]:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]
def union(x, y):
    parent_x = find(x)
    parent_y = find(y)
    if parent_x < parent_y:
        parent[y] = parent_x
    else:
        parent[x] = parent_y

out = 0

for turn in range(1, m + 1):
    cin, cout = list(map(int, input().split()))
    if find(cin) == find(cout):
        out = turn
        break
    union(cin, cout)


print(out)

jyheo98 1년 전 4

UF 구현에 실수가 있습니다.

if parent_x < parent_y:
parent[y] = parent_x
else:
parent[x] = parent_y

if parent_x < parent_y:
parent[parent_y] = parent_x
else:
parent[parent_x] = parent_y

dashadower 1년 전 0

아하..해당 실수를 못봤네요!

정말 감사합니다!!

jyheo98 1년 전 1

python 3보단 pypy3가 더 빨라서 제출언어를 바꾸면 시간초과도 해결될 듯합니다 ㅎㅎ

dashadower 1년 전 0

아하..과제로 낸 문제인데 pypy3는 사용 불가능하다고 명시하셔서..

jun2korea 1년 전 3

Python3 시간 초과부분이 문제라면 find 함수를 수정해서 해결할 수 있습니다.

find함수를 지금 재귀로 구현하였는데, 해당 부분을 완전히 같은 역할을 하게 while문으로 구현할 수 있습니다

코드도 매우 간단해요

def find(x):

    while x != parent[x]:

        x = parnet[x]

    return x

Python으로 UF문제에서 find부분을 재귀로하면 시간초과가 나오는 경우가 많습니다. find부분만 이 코드처럼 수정하면 거의 해결 가능합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Union-Find로 구현했는데 어떤 부분에서 틀리는지 모르겠습니다

dashadower 1년 전 2

jyheo98 1년 전 4

dashadower 1년 전 0

jyheo98 1년 전 1

dashadower 1년 전 0

jun2korea 1년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말