Union Find Definition

A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

Union: Join two subsets into a single subset.

What is Union Find used for?

1. It is used to keep track of connected component in an undirected graph.
2. It is used to detect cycles in the graph.
3. It is used to calculate the minimum spanning tree in Kruskal's algorithm.
4. Calculating mutual friends.

Union-Find Operation

1. init(x)
   • x를 유일한 원소로 하는 새로운 집합 구성
   • Ex. Array[i] = i
2. union(x)
   • x와 y의 집합을 합함
3. find(x)
   • x의 집합을 찾기

Union-Find Process

Simple Implementation of Union-Find

root = [i for i in range(MAX_LEN)]

def find(x):
    if root[x] == x:
        return x
    else:
        return find(root[x])

def union(x, y):
    x = find(x)
    y = find(y)
    root[y] = x

Above implementations are simple but not optimized.

Find operation optimization