[백준][Python] 20040번 사이클 게임 - 코팩

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

20040번: 사이클 게임

풀이

사이클이 생기는지에 대해서 확인해보는 문제.

- BFS는 간선을 추가한 그래프를 처음부터 계속 탐색해야하기에 부담이 크다.

- 분리 집합을 사용해서 사이클이 생기는지 확인하도록 했다.

분리집합 알고리즘

https://sunghyun98.tistory.com/256

[알고리즘] 분리 집합

 

코드

# 20040번 사이클 게임
# 사이클이 생기는지에 대한 확인을 위해 분리집합을 사용할 것이다. bfs는 시간소모가 너무크다.
import sys

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

def union(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

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

ans = 0
for i in range(m):
    x, y = map(int, sys.stdin.readline().split())
    # 부모가 같다면 사이클 구성한다.
    if find_parent(x) != find_parent(y):
        union(x, y)
    else:
        ans = i + 1
        break
print(ans)

 

출력결과