글 읽기 - 시간초과

boompatron 1년 전 0

계속 시간초과가 납니다

이름이 들어온 순서대로 딕셔너리에 번호 부여해서 union find 하는데...

어디서 시간이 초과가 난 걸까요ㅠㅠㅠ

import sys


def get_parent(p, x):
    if p[x] != x:
        p[x] = get_parent(p, p[x])
    return p[x]


def union_parent(p, a, b):
    a = get_parent(p, a)
    b = get_parent(p, b)
    if a > b:
        p[a] = b
    elif a < b:
        p[b] = a
    else:
        return


def solution():
    t = int(sys.stdin.readline().rstrip())
    while t:
        f = int(sys.stdin.readline().rstrip())
        d, parent = {}, []
        for i in range(f):
            f1, f2 = map(str, sys.stdin.readline().rstrip().split())
            if f1 not in d:
                d[f1] = len(d.keys())
                parent.append(d[f1])
            if f2 not in d:
                d[f2] = len(d.keys())
                parent.append(d[f2])
            if get_parent(parent, d[f1]) != get_parent(parent, d[f2]):
                union_parent(parent, d[f1], d[f2])
            cnt = 0
            f1_p, f2_p = get_parent(parent, d[f1]), get_parent(parent, d[f2])
            for p in range(len(parent)):
                cur_p = get_parent(parent, p)
                if cur_p == f1_p or cur_p == f2_p:
                    cnt += 1
            print(cnt)
        t -= 1


if __name__ == "__main__":
    solution()

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

문제

문제

출처

ICPC

시간초과

boompatron 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말