백준 20040 사이클 게임 - 파이썬

문제.

풀이.

유니온 파인드를 이용해서 풀면된다.

우선 생각해야 할게

유니온 연산을 하기전에 파인드 연산을 먼저해서 둘의 루트 노드가 같다면 사이클이 완성된것이다.

예를 들어

parent = [0, 1, 2, 3, 4, 5] 가 있고

이제부터 입력을 받는다고 한다면

0 1이 들어오면 둘의 파인드 연산을 했을때는 각각 루트 노드가 0 , 1이다

둘의 루트 노드가 다르니 유니온 연산을 시행한다

1, 2 입력이 들어오면 둘의 파인드 연산 결과는 0, 2

2, 3 입력이 들어오면 둘의 파인드 연산 결과는 0, 3

0, 3 입력이 들어오면 둘의 파인드 연산 결과는 0, 0 이므로 사이클이 완성됐다.

 

소스코드.

	import sys
	def union(a, b):
	a = find(a)
	b = find(b)
	if a < b:
	parent[b] = a
	else:
	parent[a] = b
	def find(target):
	if target == parent[target]:
	return target
	parent[target] = find(parent[target])
	return parent[target]
	input = sys.stdin.readline
	n, m = map(int, input().split())
	parent = [i for i in range(n)]
	isTrue = False
	for i in range(m):
	x, y = map(int, input().split())
	# 유니온 연산 전 먼저 둘의 루트 노드 체크 같다면 사이클이 완성됐으므로 break
	if find(x) == find(y):
	isTrue = True
	print(i+1)
	break
	union(x, y)
	if not isTrue:
	print(0)

view raw 사이클 게임.py hosted with ❤ by GitHub