백준 20040번: 사이클 게임 (Python)

접근

이번 문제에서는 유니온파인드 알고리즘을 이용하여 풀 수 있다.

유니온파인드 알고리즘 설명: 2021.05.01 - [코딩/백준 (Python)] - 백준 1717번: 집합의 표현 (Python)

백준 1717번: 집합의 표현 (Python)

유니온파인드 알고리즘을 수행하면서 i 번째 단계에서 주어진 두개의 수의 루트 노드가 같으면 싸이클이 이루어지므로 i를 출력해주고 연산을 마친다.

코드

import sys


def find(x):
    if connect[x] < 0:
        return x
    p = find(connect[x])
    connect[x] = p
    return p


def union(x, y):
    if connect[x] < connect[y]:
        connect[x] += connect[y]
        connect[y] = x
    else:
        connect[y] += connect[x]
        connect[x] = y


sys.setrecursionlimit(10 ** 9)
n, m = map(int, sys.stdin.readline().split())
connect = [-1 for i in range(n)]
i = 0
ans = 0
while i != m:
    a, b = map(int, sys.stdin.readline().split())
    ar = find(a)
    br = find(b)
    if ar == br:
        ans = i + 1
        break
    else:
        union(ar, br)
    i += 1
print(ans)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!