[Cos Pro 1급, Python] 5차 7번 : 그래프에서 싸이클 찾기

문제

그래프의 노드 수와 노드 연결 순서가 주어질 때, 몇 번째 연결에 사이클이 생기는지 알고 싶습니다. 예를 들어, 노드가 3개이고 노드를 [[1, 2], [1, 3], [2, 3]] 순으로 연결한다면 아래 그림과 같습니다.

• 1번째 연결

• 2번째 연결

• 3번째 연결

따라서 3번째 연결에서 사이클이 생깁니다.

그래프의 노드 수 n, 노드 연결 순서 connections와 connections의 길이 connections_len이 매개변수로 주어질 때, 몇 번째 연결에 사이클이 생기는지 return 하도록 solution 함수를 작성하려 합니다. 빈칸을 채워 전체 코드를 완성해주세요.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

def find(parent, u):
	if u == parent[u]:
		return u
	parent[u] = find(parent, parent[u])
	return parent[u]

def merge(parent, u, v):
	u = find(parent, u)
	v = find(parent, v)
	if u == v:
		return True
	parent[u] = v
	return False

def solution(n, connections):
	answer = 0
	parent = [i for i in range(n + 1)]
	for i, connection in enumerate(connections):
		if merge(parent, connection[0], connection[1]):
			answer = i + 1
			break
	return answer
    
    
    
    

n = 3
connections = [[1, 2], [1, 3], [2, 3]]
ret = solution(n, connections)

print("solution 함수의 반환 값은", ret, "입니다.")