[그래프] union-find 알고리즘

서로소 집합 disjoint sets 라고 불리기도 하고 union-find라고 불리기도 하는 알고리즘은

union과 find 연산을 통해 각 집합을 묶어주기도 하고 각 원소들이 어떤 집합에 있는지 확인하기도 하는.. 그런 알고리즘이다

 

원리는 되게 간단한데 트리를 이용하는 것이다.

처음에 모든 원소는 자기 자신을 부모노드로 가리키게 된다.

만약 a와 b의 union 연산이 발생하면

a와 b의 부모노드, 그 부모노드의 부모노드, 그 부모노드의.. 계속 추적해서 루트노드를 찾아낸다.

루트노드는 자기 자신을 부모로 가지고 있을 것이다.

그리고 그 a와 b의 루트노드가 다르다면 둘은 서로 다른 집합에 속해있는 것이고

b의 부모노드를 a로 설정해 둘을 한 집합으로 만드는 것이다.

 

다음은 이 간단한 원리로 disjoint_set 클래스를 만든것이다.

class disjoint_set:
    def __init__(self, num_of_elements):
        self.parent = [i for i in range(num_of_elements)]

    def find(self, element_index):
        if self.parent[element_index] != element_index:
            self.parent[element_index] = self.find(self.parent[element_index])
        return self.parent[element_index]

    def union(self, element1_index, element2_index):
        parent1 = self.find(element1_index)
        parent2 = self.find(element2_index)

        self.parent[max(parent1,parent2)] = min(parent1,parent2)

    def print_parent(self):
        print("parent list",self.parent)


v, e = map(int, input().split())
ds = disjoint_set(v)

for i in range(e):
    a, b = map(int, input().split())
    ds.union(a, b)

for i in range(v):
    print("parent of",i,"is",ds.find(i))

ds.print_parent()