[알고리즘]백준 20040 : 사이클 게임 (파이썬)

20040번: 사이클 게임

무방향 그래프에서 간선이 계속 주어지고, 사이클이 발생하면 해당 count를 출력하는 문제

처음에는 분리집합 문제로 이해했고 Union, Find를 사용하면 간단히 풀릴 것으로 생각했다.
어제 공부했던 MST 알고리즘에서 작성했던 코드를 참고하여 코드를 작성했는데, 예상한 답이 나오지 않아서
DFS로 접근을 바꾸어 DFS를 계속 수행하면서 방문한 정점을 계속 기록하고, 방문한 정점을 또 방문했을 때 사이클이 존재하는 것으로 간주했다.

이 때 dfs 함수 내에 global count 변수를 지정하고 호출시마다 1씩 더해나가는 방법을 사용했는데, 풀리지 않았다. 다시 처음 이해한 Union/FInd 로 접근해서 문제를 해결했다. DFS로도 풀 수 있을 것 같은데 DFS를 더 공부하고 DFS로 풀어보아야겠다.

++ 백준 질문 게시판에서 재귀로 구현한 find(x)보다 while문으로 구현한 find 함수가 효율적이라는 글을 발견했다. 앞으로 재귀적으로 find(x)를 호출하지 않고 while문을 활용한 find 함수를 사용해야겠다.

import sys

input = sys.stdin.readline

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

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

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

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