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

사이클 판별

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

판별 알고리즘

1. union 연산은 간선을 의미, 간선을 확인하고, 두 노드의 루트를 확인
   1. 루트 노드가 다른 경우 두 노드에 대해 union → 동일한 세트로 설정합니다.
      
      
   2. 루트 노드가 같으면 → 사이클 발생
2. 그래프의 모든 간선(E)에 대해 한 번의 처리 반복

동작 예

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

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

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

3. 간선(1,3) 확인 → 노드 1의 부모는 1노드 3의 부모는 3이므로 더 큰 번호를 가진 노드 3의 부모를 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("사이클이 발생하지 않았습니다.

")