CHAPTER 10. 그래프 이론 - 서로소 집합의 사이클 판별

사이클 판별

• 무방향 그래프: 서로소 집합으로 사이클 판별 가능
• 방향 그래프: DFS를 이용하여 사이클 판별 가능

판별 알고리즘

1. union 연산은 간선을 의미, 간선을 확인하며 두 노드의 루트를 확인
   1. 루트 노드가 다르면 → 두 노드에 대해 union  →  같은 집합으로 만든다.
   2. 루트 노드가 같다면 → 사이클이 발생
2. 그래프의 모든 간선(E)에 대해서 1번 과정을 반복

동작 예시

1. 부모 테이블의 모든 노드에 대해 자기 자신을 부모로 설정

노드 번호	1	2	3
부모 노드 번호	1	2	3

간선을 하나씩 확인해서 간선을 구성하는 노드에 대해 합집합 연산을 수행

2. 간선 (1, 2) 확인 → 노드1의 부모는 1 노드2의 부모는 2이므로 더 큰 번호를 가지는 노드2의 부모를 1로 갱신

노드 번호	1	2	3
부모 노드 번호	1	1	3

3. 간선 (1, 3) 확인 → 노드1의 부모는 1 노드3의 부모는 3이므로 더 큰 번호를 가지는 노드3의 부모를 1로 갱신

노드 번호	1	2	3
부모 노드 번호	1	1	1

4. 간선 (2, 3) 확인 → 노드2의 부모는 1 노드3의 부모는 1 = 이미 같은 집합 = 사이클 발생

구현

# 서로소 집합을 활용한 사이클 판별 소스코드
# 특정 원소가 속한 집합을 찾기, 경로 압축 기법
def find_parent(parent, node):
  if parent[node] != node:
    parent[node] = find_parent(parent, parent[node])
  return parent[node]

# 두 원소가 속한 집합 합치기
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

v, e = map(int, input().split()) # 노드 개수, 간선(unoin) 개수 입력
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()) # 간선에 해당하는 노드 2개
  # 이미 같은 집합이라면, 사이클이 발생한 것이므로 종료
  if find_parent(parent, a) == find_parent(parent, b):
    cycle = True # 사이클 발생
    break
  # 사이클이 발생하지 않았다면 union
  else:
    union_parent(parent, a, b)

# 사이클 발생 여부 출력
if cycle:
  print("사이클이 발생했습니다.")
else:
  print("사이클이 발생하지 않았습니다.")