서로소 집합 자료구조

출처:www.youtube.com/watch?v=aOhhNFTIeFI

---

<서로소 집합 자료구조>

- 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미

ex. {1,2}와 {3,4}는 서로소 관계이고, {1,2}와 {2,3}은 서로소 관계가 아니다.

 

- 서로소 판별을 위해 사용할 수 있는 자료구조

- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

- 서로소 집합 자료구조는 두 종류의 연산을 지원

    1. 합집합(Union): 두 개의  원소가 포함된 집합을 하나의 집합으로 합치는 연산

    2. 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

- 서로소 집합 자료구조는 합치지 찾기(Union Find) 자료구조라고 불리기도 함

 

[여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작과정]

1. 각각의 합치기(Union)연산을 확인하여, 서로 연결된 두 노드 A, B를 확인

    1) A와 B의 루트 노드들을 각각 찾는다.

    2) 해당 루트노드들을 부모 노드로 설정

2. 모든 합집합(Union)연산을 처리할 때까지 1번의 과정을 반복

(초기) 부모 - 자기 자신

1. union연산 하나 수행, 더 큰 번호에 해당하는 루트 노드의 부모를 작은 노드로 설정

2. 이미 갱신이 되었다면 부모가 작은쪽으로

3. 연산 종료 후 연결성을 통해 쉽게 집합의 형태 확인 가능

[서로소 집합 자료구조: 연결성]

- 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없음

     : 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야 한다.

 

#Python Union Find


def find_parent(parent, x):#특정 원소가 속한 집합을 찾기
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return 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
   
#union연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)
    
#각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ' , end=' ')
for i in range(1, v+1):
    print(find_parent(parent, i), end = ' ')
print()

#부모 테이블 내용 출력
print('부모 테이블: ' , end = ' ')
for i in range(1, v+1):
   print(parent[i], end =' ')

int v, e; //노드의 개수(v)와 간선(union 연산)의 개수(e)
int parent[100001];

int findParent(int x){ //특정 원소가 속한 집합 찾기
    if (x == parent[x]) return x;
    return findParent(parent[x])
}

void unionParent(int a, int b){ //두 원소가 속한 집합을 합치기
    a = findParent(a)
    b = findParent(b)
    if (a<b) parent[b] = a;
    else parent[a] = b;
}
int main(){
    cin >> v >> e;
    for(int i= 1; i <=v; i++){
        parent[i] = i;
    }
    
    //union연산 수행
    for(int i=0; i <e; i++){
        int a,b;
        cin >> a>> b;
        unionParent(a, b);
    }
    
    //각 원소가 속한 집합 출력
    cout << "각 원소가 속한 집합: ";
    for(int i = 1; i <=v; i++){
        cout <<findParent(i) <<" ";
    }
    
    //부모 테이블 출력
    cout >> "부모 테이블: " ;
    for(int i= 1; i <=v; i++){
        cout << parent[i] <<" ";
    }
}

[기본적인 구현 방법의 문제점]

- 합집합(Union)연산이 편향되게 이루어지는 경우 찾기(Find)함수(매번 부모 테이블을 참조, 부모에 대해 재귀적 호출) 가 비효율적으로 동작함

- 최악의 경우에는 찾기(Find)함수가 모든 노드를 다 확인하게 되어 시간 복잡도가 O(V)

-> 경로 압축!!

 

[경로 압축]

- 찾기(Find)함수를 최적화하기 위한 방법으로 경로 압축(Path Compression)을 이용할 수 있음

    : 찾기(Find)함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신

def find_parent(parent, x):
    if parent[x] != x: #루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적 호출
        parent[x] = find_parent(parent,  parent[x])
    return parent[x]

int findParent(int x){
     if(x == parent[x]) return x;
     return parent[x] = findParent(parent[x]);
}

- 경로 압축 기법을 적용하면 각 노드에 대하여 찾기(Find)함수를 호출한 이후에 해당 노드의 루트 노드가 바로 부모 노드가 됨

- 모든 합집합(Union)함수를 처리한 후 각 원소에 대하여 찾기(Find)함수를 수행

- 시간 복잡도 개선

---

<서로소 집합을 활용한 사이클 판별>

- 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있음

   : 참고로 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있음

- 사이클 판별 알고리즘

    1. 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인

        1) 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행

        2) 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것

     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): #두  원소가 속한 집합을 합치기
    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 #사이클 발생 여부

#union연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    #사이클 발생시  종료
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    #사이클이 발생하지 않았다면 합집합(union)연산 수행
    else:
        union_parent(parent, a, b)
    
if cycle:
    print("사이클 발생")
else:
    print("사이클 발생 x")