문제
접근
사이클 여부를 체크하는 문제이다.
사이클을 확인하는 알고리즘은 유니온-파인드 알고리즘이 있다.
유니온-파인드 알고리즘은 그래프 알고리즘의 하나로써, 상호 배타적 집합이라고도 부른다.
유니온-파인드 알고리즘은 최초에 자기 자신을 루트 로드로 가지는 트리 형태로 시작한다.
모든 노드들이 하나의 트리를 가지고 있는 셈이다.
그 상태에서 두 개의 노드를 연결한다면 두 노드는 하나의 트리로 합쳐지는 방식이다.
이렇게 합치는 과정을 연산하기 위한 union 함수와 합치는 과정에서 두 노드의 루트 노드를 찾는 find 함수로 이루어져 있다.
find 함수는 인자로 전달받는 노드의 루트 노드를 찾아서 반환해준다.
루트 노드를 찾는 과정에서 재귀 방식을 사용하는데, 트리가 한쪽으로만 치우쳐진 경우에 루트 노드를 찾는데 O(N) 시간이 소요된다.
이를 방지하기 위해 루트 노드를 찾는 과정에서 모든 노드들의 부모를 루트 노드로 바꿔주는 작업을 수행한다.
이러면 모든 노드에서 루트 노드를 찾을 때 O(1) 시간만 소요된다.
Union 함수의 경우에는 두 개의 노드를 입력받아서 각 노드가 속해있는 트리(집합)을 한 개의 트리로 합쳐주는 역할을 수행한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import sys
input = sys.stdin.readline
n, e = map(int, input().split(' '))
parent = [-1 for _ in range(n)]
def find_parent(x):
if parent[x] < 0:
return x
else:
y = find_parent(parent[x])
parent[x] = y
return y
def union(x, y):
x = find_parent(x)
y = find_parent(y)
if x == y:
return True
if parent[x] < parent[y]:
parent[x] += parent[y]
parent[y] = x
else:
parent[y] += parent[x]
parent[x] = y
return False
ans = 0
for i in range(e):
node1, node2 = map(int, input().split(' '))
isCycle = union(node1, node2)
if isCycle:
ans = i+1
break
print(ans)