개요
n개의 정점이 주어지고, 무방향의 m개의 간선을 잇습니다. 이때 사이클이 발생하면 몇번째 간선을 그을때 발생했는지 출력하면 되는 문제입니다.
문제풀이
접근
분리 집합, 유니온 파인드, 서로소 집합으로 풀 수 있는 문제입니다. 셋이 같은 의미로 사용되더군요. 공통되지 않은 요소들을 가지고 있는 두 집합을 비교하거나 합칠 때 주로 사용하는 자료구조입니다. 특징으로 사이클이 발생했는지 판별할 수 있기 때문에 사용했습니다.
왜냐하면 각 정점들이 같은 부모를 가지고 있으면 하나의 집합임을 알 수 있습니다. 만약 두 정점이 이미 같은 집합일때 (같은 부모를 가지고 있을때), 두 정점을 이으면 사이클이 발생합니다. 이 전제를 가지고, 표를 그려보겠습니다.
간선을 이음에 따라 변화하는, 각 정점의 부모를 기록한 표입니다.
- 처음에는 정점들끼리 아무것도 이어지지 않고 독립된 상태로 존재하므로, 자기 자신이 부모입니다. (첫번째 행)
0과1을 잇는다면,0이1보다 작으므로0이1의 부모가 됩니다.1과 다른 숫자들(2, 3)을 이을때1의 부모인0보다 작은 숫자가 없으므로, 모두 부모가0이 됩니다.- 5번째 행에서
0과3이 이미 같은 부모를 공유하고 있는데 서로 이으려는게 보입니다. 이때 사이클이 발생합니다.
코드 구현
# 루트 노드의 특징은 자기 자신이 부모입니다. 루트 노드를 찾을때까지 재귀적으로 파고 듭니다.
def find_parent(x):
if parent[x] != x:
parent[x] = find_parent(parent[x])
return parent[x]
# 작은 숫자가 부모가 됩니다.
def union(a, b):
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [i for i in range(v)]
cycle=0
for i in range(1, e+1):
a, b = map(int, input().split())
parent_a = find_parent(a)
parent_b = find_parent(b)
if parent_a == parent_b:
cycle=i
break
else:
union(parent_a, parent_b)
print(cycle)
[[2022-06-27-백준-12852-1로-만들기-2]]