20040 사이클게임 (python)

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

20040번: 사이클 게임

 

 

 

 

 

문제 접근

운이 좋았나... 바로 union & find가 떠올랐다.

이었을때 두 점이 둘다 같은 부모를 가르킨다면 사이클이 돌고있다는 뜻.

그때를 출력하면된다

코드는 생각나는대로 쭉 썼는데 시간도 여유롭게 통과됐다

 

 

 

 

 

코드

import sys
input = sys.stdin.readline


"""

"""

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
        return parent[x]
    return x

def union(a,b):
    x = find(a)
    y = find(b)
    if x==y: 
        return 0
    elif x<y: 
        parent[y] = x
    else: 
        parent[x] = y
    return 1


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

for i in range(m):
    x, y = map(int,input().split())
    a = union(x,y)
    if a==0:
        print(i+1)
        break;
else:
    print(0)

 

줄이려면 줄일 요소가 많은듯