[백준] 20040번 사이클 게임 파이썬 코드

코드

# 사이클 판별
# 무방향 그래프인 경우 유니온 파인드로 사이클을 판별할 수 있다
# 참고로 유향 그래프인 경우에는 dfs로 판별할 수 있다

import sys
sys.setrecursionlimit(10**5) # 재귀 깊이 제한
input = sys.stdin.readline # 빠른 입력

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

def find(x,lst): # 트리의 루트 노드를 찾아주는 find 함수
  if x != lst[x]:
    lst[x] = find(lst[x], lst)
  return lst[x]

def union(x,y,lst): # 트리를 합쳐주는 union 함수
  x = find(x,lst)
  y = find(y,lst)
  if x<y:
    lst[y] = x
  else:
    lst[x] = y

for i in range(1,m+1):
  a,b = map(int, input().split())
  #루트 노드가 같으면 == 이 노드를 이으면 사이클이 생기는 경우
  if find(a, parent) == find(b, parent):
    print(i) # 횟수를 출력하고 종료
    break
  union(a,b,parent)
else: print(0)

루트 노드가 같으면 사이클이 생긴다. 아래 그림을 보면 이해하기 쉬울 듯하다.

A-B, A-C 간선이 있는 경우

B-C를 이으려는 경우, B와 C는 루트 노드가 같다

참고

https://lordofkangs.tistory.com/340