간선을 추가하며 두 정점이 이미 연결됐는지 반복 확인합니다. Union-Find는 무엇을 저장하나요?

Union-Find는 원소를 서로 겹치지 않는 집합으로 나누어 저장하고, 두 원소의 대표자가 같은지로 같은 연결 성분인지 빠르게 확인합니다. 간선을 추가할 때 양 끝의 대표자가 다르면 두 집합을 합치고, 같으면 이미 다른 간선들로 연결돼 있어 그 간선을 추가하면 사이클이 생깁니다. 실제 경로의 중간 정점을 저장하거나 경로를 복원하는 구조는 아닙니다.

지원 범위와 동시 갱신을 확인합니다

각 원소에 부모 포인터를 두고 루트가 자기 자신을 가리키게 합니다. find(x)는 부모를 따라 루트 대표자를 찾고, union(a,b)는 두 대표자를 찾아 한 트리를 다른 트리에 붙입니다. 무작정 붙이면 긴 사슬이 생기므로 작은 집합을 큰 집합에 붙이거나 rank가 낮은 트리를 높은 트리에 붙입니다. find 중 지나간 노드의 부모를 루트로 바로 바꾸는 경로 압축도 함께 사용합니다. 이 조합의 긴 연산열 비용을 분할 상환 역 아커만 시간(inverse-Ackermann amortized time) 수준이라고 설명할 수 있지만, 각 호출이 엄밀한 상수 시간이라는 표현은 피하겠습니다.

예를 들어 간선을 순서대로 검사하는 Kruskal에서는 두 끝이 이미 같은 대표자를 갖는지 보고 사이클 간선을 건너뜁니다. 두 집합을 합친 뒤 집합 크기·합계·최소 ID 같은 메타데이터가 필요하면 대표자에 붙여 관리하되, 대표자가 항상 최소 원소이거나 서비스에서 의미 있는 리더라는 보장은 없습니다. 대표자가 바뀌어도 외부 식별자가 안정적이어야 한다면 별도 값을 둡니다.

지원 범위와 실패 조건을 분명히 합니다

기본 Union-Find는 집합을 합치는 작업에는 강하지만 간선을 삭제해 연결을 다시 나누는 동적 연결성에는 맞지 않습니다. 방향 그래프의 경로·강한 연결성, 두 정점 사이 실제 경로 반환도 이 구조만으로 해결하지 못합니다. 롤백이 필요하면 변경 스택을 두고 경로 압축을 제한하거나 되돌릴 수 있는 방식으로 구현해야 합니다.

테스트는 자기 자신과 union, 이미 같은 집합의 재합치, 긴 합치기 순서, 집합 메타데이터, 연결되지 않은 성분을 포함합니다. 간선 추가 뒤 find 결과가 기대한 분할과 같은지 확인하고, Kruskal과 결합할 때 선택 간선 수가 성분 수에 맞는지도 보겠습니다. 대표자 번호 자체를 결과 의미로 노출하지 않는 것이 안전합니다.

Union-Find는 부모 포인터와 대표자만 저장하므로 두 정점이 같은 집합인지 알려 주지만 실제 연결 경로는 주지 않습니다. 크기 기반 합치기와 경로 압축을 함께 쓰면 긴 연산열 비용이 매우 작아지지만, 합치기 순서에 따라 대표자는 바뀝니다. 집합별 크기·합계가 필요하면 살아남은 루트에 메타데이터를 합치고 사라진 루트의 값은 외부 결과로 사용하지 않겠습니다.

현재 부모 배열의 복사본은 복사한 순간의 상태를 보존하는 스냅샷입니다. 그 스냅샷 시점의 조회를 재현할 수는 있지만, 합치기 이전 상태로 자동 복원하는 변경 이력은 아닙니다. 과거 상태로 되돌리려면 합치기 변경을 별도 스택에 기록하는 롤백 구조가 필요하고, 경로 압축처럼 부모를 바꾸는 최적화도 그 기록과 충돌할 수 있습니다. 간선 삭제·방향 경로·실제 경로 복원이 필요하면 다른 구조를 선택하겠습니다.

오프라인으로 전체 추가·삭제 시점을 안다면 각 간선이 살아 있는 시간 구간을 구한 뒤 시간 구간 트리를 순회하며 rollback Union-Find를 쓰는 방법도 있습니다. 구간에 들어갈 때 union하고 나올 때 변경 스택을 되돌리면 각 시점의 질의를 처리할 수 있습니다. 이는 미래 입력을 모르는 온라인 삭제를 기본 Union-Find가 직접 지원한다는 뜻은 아닙니다.