1. 서로소 집합은 무방향 그래프 내에서 사이클을 판별할 때 사용할 수 있습니다.
참고로 방향 그래프에서의 사이클 여부는 DFS를 이용해서 판별할 수 있습니다.
사이클 판별 알고리즘은 아래와 같습니다.
2. 입력받은 각 간선 정보를 하나씩 확인하며 두 노드의 루트 노드를 확인합니다.
1) 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행합니다.
2) 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것입니다.
3. 그래프에 포함되어 있는 모든 간선에 대하여 2번 과정을 반복합니다.
[초기단계] 모든 노드에 대하여 자기 자신을 부모로 설정하는 형태로 부모 테이블을 초기화 해줍니다.
| 인덱스 | 1 | 2 | 3 |
| 부모 | 1 | 2 | 3 |
[Step 1] 간선 (1,2)을 확인합니다. 노드 1과 노드 2의 루트 노드는 각각 1과 2입니다. 여기서 더 큰 번호에 해당하는 노드 2의 루트 노드 (부모 노드)를 1로 변경해 줍니다.
| 인덱스 | 1 | 2 | 3 |
| 부모 | 1 | 1 | 3 |
[Step 2] 간선 (1,3)을 확인합니다. 노드 1과 노드 3의 루트 노드는 각각 1과 3입니다. 따라서 더 큰 번호에 해당하는 노드 3의 루트 노드 (부모 노드)를 1로 변경합니다.
| 인덱스 | 1 | 2 | 3 |
| 부모 | 1 | 1 | 1 |
[Step 3] 마지막으로 간선 정보 (2,3)을 확인합니다. 이미 노드 2과 노드3의 루트 노드는 모두 1로써, 이미 같은 집합에 포함되어있다고 판단할 수 있습니다. 다시 말해, 두 노드에 대한 간선을 처리하려는데 두 노드가 같은 부모 노드를 갖고 있다면 이는 사이클이 발생한 것으로 판별할 수 있습니다.
[서로소를 활용한 사이클 판별 코드]
# 특성 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드를 찾을 때까지 재귀 호출 (부모의 루트 노드 탐색)
if parent[x] != x:
parent[x] = find_parent(parent, parent[x]) # 경로 압축
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
# 작은값이 부모루트가 되도록 지정
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선 (Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화 하기
# 부모 테이블 상태에서 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
Cycle = False
for i in range(e):
a, b = map(int, input().split())
# 사이클이 발생한 경우 종료
if find_parent(parent,a) == find_parent(parent, b):
Cycle = True
break
else:
union_parent(parent,a,b)
if Cycle:
print('사이클이 발생했습니다')
else:
print('사이클이 발생하지 않았습니다.')