분리 집합

분리 집합 (Disjoint Set) / Union-Find

다음과 같은 메신저 프로그램이 있다. "A와 B가 친구 관계이고, 내가 A와 친구 관계이면 자동으로 나와 B는 친구 관계가 된다." 이 메신저 프로그램을 통해 내가 A라는 사람과 친구 관계를 맺었다. 다음과 같은 관계도에서, 내가 주황색으로 표시된 사람과 친구 관계가 될 수 있을지는 어떻게 알 수 있을까? 위처럼 친구 관계를 그래프로 나타낸 후 나를 시작으로 그래프 탐색(DFS, BFS)을 통해 목표 정점까지 도달할 수 있는지 확인하면 간단할 것이다. 하지만 새로운 친구 관계는 언제나 생겨날 수 있다. 만약 주황색으로 표시된 친구 관계가 새로 생겼다고 할 때, 우리는 주황색 사람과 친구 관계가 될 수 있는지 알기 위해서다시 그래프 탐색을 진행해야 한다. 하지만 이 메신저 프로그램을 사용하는 사용자의 수가..