[BOJ] 20040. 사이클 게임

www.acmicpc.net/problem/20040

20040번: 사이클 게임

 

문제: 사이클이 생긴다면 그 즉시, 해당 번호를 출력하라.

 

문제 이해하기!!

처음에는 이게 무슨 문젠가 싶었어요.

일단 그래프 문젠데... 연결해서 사이클이면 어떻게 해야하지 라고 생각했었는데

아니;; 그래프 문젠줄알고 들어가서 풀었는데 분리집합이더라구요.

들어오는 것들 union으로 싹 다 넣어서 부분 집합을 통일시키면 되는데,

들어오기 전에 둘의 부모가 같아서 이미 해당 부분집합에 들어가 있는 두 숫자라면

무조건 사이클이 생기는 경우죠! 이건 좀 생각해보셔야 할 수도 있슴당^^

 

코드:

from sys import stdin
input = stdin.readline
import sys
sys.setrecursionlimit(200000)

def find(x):
    if x == arr[x]:
        return x
    else:
        arr[x] = find(arr[x])
        return arr[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        arr[y] = x
    else:
        arr[x] = y

N, M = map(int, input().split())
arr = [i for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    if find(a) == find(b):
        print(i+1)
        break
    union(a, b)
else:
    print(0)