[백준 20040] 사이클 게임

 

 

문제

---

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

20040번: 사이클 게임

 

 

나의 풀이

---

전형적인 유니온 파인드(union find) 문제이다. 유니온 파인드 알고리즘은 그래프가 사이클을 갖는지 여부를 판별하는 알고리즘이다.

약간 헷갈렸던 부분이 사이클을 판별하기 위해선 연결하려는 두 노드 x,y가 같은 부모를 갖는지를 먼저 확인하고 unionParent 함수를 call해야 된다는 점이다. 처음에 unionParent를 먼저 실행하고 isSameParent를 실행했다가 틀렸다.

파이썬의 경우 재귀 함수의 최대 깊이로 인해 처음 제출하면 Runtime error가 나는데 setrecursionlimit을 설정해주면 된다.

 

코드

---

# https://www.acmicpc.net/problem/20040
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def getParent(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = getParent(parent[x])
        return parent[x]

def unionParent(x,y):
    x_parent = getParent(x)
    y_parent = getParent(y)
    if x_parent < y_parent:
        parent[x_parent] = y_parent
    else:
        parent[y_parent] = x_parent

def isSameParent(x,y):
    if getParent(x) == getParent(y):
        return True
    else:
        return False

node, turn = map(int, input().split())
edge = []
for _ in range(turn):
    edge.append((tuple(map(int, input().split()))))
parent = [i for i in range(node)]
cnt = 0
done = False
for x,y in edge:
    cnt += 1
    if isSameParent(x,y):
        print(cnt)
        done = True
        break
    unionParent(x,y)
if not done:
    print(0)