백준_20040_사이클 게임

문제

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

20040번: 사이클 게임

풀이

분리집합

이미 같은 집합에 있는 원소(부모가 같은 원소)들이 언급되었다면, 사이클이 생긴 것이다.

 

코드

def find(n) : 
    if parent[n]==n : return n
    parent[n] = find(parent[n])
    return parent[n]

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

def main(n, m, arr) : 
    for i, (x, y) in enumerate(arr) : 
        if find(x)==find(y) : return i+1
        union(x, y)
    return 0

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = map(int, input().strip().split())
parent = [i for i in range(n)]
arr = [map(int, input().strip().split()) for i in range(m)]
print(main(n, m, arr))