[그래프] 서로소 집합으로 사이클 판별하기

해당 포스팅은 나동빈님의 이코테 강의를 듣고 정리한 내용입니다.

 

• 서로소 집합은 무방향 그래프 내에서의 사이클 판별에 사용될 수 있다.
• 방향 그래프의 사이클 판별 여부는 DFS를 사용한다.

 

사이클 판별 알고리즘

1. 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다.
   • 루트 노드가 서로 다르다면 두 노드에 대해 합집합(union) 연산을 수행한다.
   • 루트 노드가 서로 같다면 사이클이 발생한 것이다.
2. 그래프에 포함되어 있는 모든 간선에 대하여 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):
    root_a = find_parent(parent, a)
    root_b = find_parent(parent, b)
    if root_a < root_b:
        parent[b] = root_a
    else:
        parent[a] = root_b

# 입력
v, e = map(int, input().split())
parent = [i for i in range(v+1)]

cycle = False  # 사이클 여부
for _ 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('사이클이 존재하지 않습니다')

위에서 구현한 서로소 집합 알고리즘과 동일하고, 사이클 판단 여부만 추가되었다.