[COS PRO 1급 #5-7] 그래프에서 싸이클 찾기

문제설명

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

 

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

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

매개변수 설명

그래프의 노드 수 n, 노드 연결 순서 connections가 solution 함수의 매개변수로 주어집니다.
* 그래프의 노드 수 n은 3 이상 10 이하입니다.
* connections은 길이가 3 이상 50 이하인 리스트입니다.
* connections 리스트의 각 행은 [a, b]는 a번 노드와 b번 노드를 연결한다는 의미입니다.
* 항상 사이클이 생기는 경우만 주어집니다.

return 값 설명

몇 번째 연결에서 사이클이 생기는지 return 합니다.

예시

| n | connections              | return |
|---|--------------------------|--------|
| 3 | [[1, 2], [1, 3], [2, 3]] | 3      |

예시 설명

문제에 나온 예와 같습니다.

문제 코드

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

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

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

풀이

# Union-Find 알고리즘: https://c4u-rdav.tistory.com/44

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