Union - Find

여러 개의 원소가 있고, 여러 개의 집합이 있다고 가정합시다. 특정 원소가 어떤 집합에 속해있는지 확인하고, 특정 집합을 합쳐야 할 일이 있다면 Union-Find 자료구조를 사용하면 좋습니다.

-> 트리가 있을 때, 노드에서 그 노드의 루트 노드(대표 노드)를 쉽게 알 수 있다.

문제링크

function init(size)
  set uf = [0] with size
  for i = 1 ... size
    uf[i] = i
  return uf

function find(x)
  if uf[x] == x
    return x
  return find(uf[x])
  
function union(x, y)
  set X = find(x), Y = find(y)
  uf[X] = Y

uf = init(6)

union(2, 3)
union(1, 4)
union(1, 5)
union(4, 2)
union(3, 1)

print(find(1))
print(find(2))
print(find(3))
print(find(4))
print(find(5))

여기서

union(2, 3)
union(1, 4)
union(1, 5)
union(4, 2)
union(3, 1)

이 부분을 해결하고 싶은 것인데

uf[] -> {1, 2, 3, 4, 5, 6} 이고

union(2, 3)
-> uf[2] = 3

union(1, 4)
-> uf[1] = 4

union(1, 5)
-> uf[4] = 5 // uf[1] = 4이기 때문에 X = 4가 된다

union(4, 2)
-> uf[5] = 3

union(3, 1)
-> uf[3] = 3 // uf[1] = 4, uf[4] = 5, uf[5] = 3

print(find(1))
-> uf[1] -> uf[4] -> uf[5] -> 3
print(find(2))
-> uf[2] -> 3
print(find(3))
-> uf[3] -> 3
print(find(4))
-> uf[4] -> uf[5] -> 3
print(find(5))
-> uf[5] -> 3

결론적으로 모든 출력이 3이 된다.