백준 20040 [사이클 게임] 파이썬

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

 

# 백준 20040 사이클 게임
# 문제 요약:
#   - n개의 노드, m개의 연결 시도
#   - 연결 도중 처음으로 사이클이 생긴 시점(몇 번째 연결인지)을 출력
#   - 사이클이 안 생기면 0 출력

import sys
sys.setrecursionlimit(10**7)  # 재귀 깊이 제한 해제
input = sys.stdin.readline

# 입력: 노드 수 n, 연결 시도 수 m
n, m = map(int, input().split())

# Union-Find parent 배열 초기화
parent = [i for i in range(n+1)]

# Find 함수 (경로 압축)
def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

# Union 함수
# - a, b를 합칠 수 있으면 True 반환
# - 이미 같은 집합이면 False 반환 (사이클 발생)
def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        parent[a] = b
        return True
    return False

succ_flag = True  # 사이클 발생 여부
cnt = 0           # 연결 시도 횟수

# 연결 시도 순서대로 처리
for i in range(1, m+1):
    a, b = map(int, input().split())
    cnt += 1
    # union이 False면 사이클 발생
    if not union(a, b):
        succ_flag = False
        break

# 결과 출력
if succ_flag:   # 모든 연결 후에도 사이클 없음
    print(0)
else:           # 사이클이 처음 발생한 연결 번호 출력
    print(cnt)

UNION-FIND를 이용하여 사이클이 생기는지 파악한다.