사이클 게임 ( 20040 번 )

20040번: 사이클 게임

 

🧠 알고리즘

m개의 간선 정보를 입력받으며 루프를 돔
두 노드가 이미 같은 집합에 속하면 → 사이클 발생 → 현재 턴 번호(answer) 반환, 아니라면 두 노드를 유니온 수행...
루프가 끝날 때까지 사이클이 없으면 0을 반환

 

🧾 코드

import sys

def _find_pt(num):
    if num != pt_list[num]:
        pt_list[num] = _find_pt(pt_list[num])
    
    return pt_list[num]


def _union(a, b):
    pt_a, pt_b = _find_pt(a), _find_pt(b)
    if pt_a > pt_b:
        pt_list[pt_a] = pt_b
    else:
        pt_list[pt_b] = pt_a


def _main(n, m):
    answer = 0
    for _ in range(m):
        answer += 1
        a, b = map(int, sys.stdin.readline().rstrip().split())
        if _find_pt(a) == _find_pt(b):
            return answer

        _union(a, b)        

    return 0

n, m = map(int, sys.stdin.readline().rstrip().split())
pt_list = [i for i in range(n)]
print(_main(n, m))

 

⏱️ 시간 복잡도

m 만큼 반복하므로 : 선형 시간 복잡도
    _find() : 경로 압축으로 거의 상수 시간
    _union() : 경로 압축으로 거의 상수 시간

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )