union find 알고리즘 활용 - 사이클을 판별하는 방법 -

1. 사이클 판별

 

서로소 집합 알고리즘은 무방향 그래프에서 사이클을 판별할 때 사용할 수 있다.

 

방향 그래프에서 사이클 여부는 DFS로 확인할 수 있다고 한다

 

핵심 원리는 union 연산이 그래프에서의 간선으로 표현될 수 있는데(두 노드를 합치므로)

 

간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것만으로 사이클을 판별할 수 있다.

 

 

2. 알고리즘

 

2-1) 각 간선을 확인하면서 두 노드의 루트 노드를 확인

 

2-1-1) 루트 노드가 서로 다르다면, 두 노드에 대해 union 연산을 수행

 

2-1-2) 루트 노드가 서로 같다면 사이클이 발생

 

2-2) 그래프에 포함된 모든 간선에 대해 위 과정을 반복

 

 

3. 예시로 이해하는 사이클 판별 알고리즘

 

3-1) 초기 단계에서는 모든 노드에 대해 자기 자신을 부모로 설정하는 부모 테이블 생성

 

 

3-2) 가장 먼저 간선 1-2를 확인. 노드 1과 노드 2의 루트 노드는 각각 1과 2이다. 루트 노드가 다르다.

 

그러므로 union 연산을 수행하여 2의 부모 노드를 1로 변경

 

 

3-3) 이어서 간선 (1,3)을 확인하고, 각각 루트 노드가 1과 3으로 서로 다르다.

 

union 연산을 수행하여 3의 부모를 1로 변경한다

 

 

3-4) 이후에 간선 (2,3)을 확인한다. 이때 노드 2와 노드 3은 이미 루트 노드로 1을 가지고 있다.

 

모든 간선을 확인하기 전에 루트 노드가 서로 같은 경우가 발생했으므로 사이클이 발생했다.

 

 4. 구현 예시

 

사이클 판별 알고리즘은 그래프에 포함되어 있는 간선의 개수가 E개이고

 

모든 간선을 하나씩 확인하면서 매 간선에 대하여 union및 find함수를 호출하는 방식으로 동작

 

이는 무방향 그래프에 대해서만 적용 가능하다

 

#반복구조로 구현한 find 함수
# 원소 x의 대표자를 찾는다

def find_parent(parent,x):
    
    while x != parent[x]:
        
        x = parent[x]
    
    return x

## union 함수
## 두 원소 a,b를 하나로 합친다

def union_parent(parent,a,b):
    
    a = find_parent(parent,a) #a의 대표자를 찾고
    b = find_parent(parent,b) #b의 대표자를 찾고

    if a < b: #더 큰 번호의 부모를 더 작은 번호로 설정
        
        parent[b] = a
    
    else:
        
        parent[a] = b

#노드의 개수와 간선의 개수

v,e = map(int,input().split())
parent = [0]*(v+1) #부모 번호를 저장할 리스트

##처음엔 자기 자신을 부모로 가지도록 초기화

for i in range(1,v+1):
    
    parent[i] = i

cycle = False ##현재 그래프에서 cycle 발생 여부


#그래프의 모든 간선을 확인
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) ##(a,b)의 union 수행

if cycle:
    
    print('사이클이 발생했습니다.')

else:
    
    print('사이클이 발생하지 않았습니다.')

"""
3 3
1 2
1 3
2 3
사이클이 발생했습니다.
"""