Dynamic Connectivity: 간선 추가/삭제 연결성
Dynamic Connectivity, 동적 연결성
정의
Dynamic Connectivity 는 간선의 추가와 삭제 가 모두 일어나는 그래프에서 두 정점의 연결 여부를 유지하는 문제입니다.
삽입만 있는 경우
Union-Find 로 O(α(N)) amortized.
삭제만 있는 경우
시간 역행으로 삽입 문제로 환원.
삽입 + 삭제
Link-Cut Tree 또는 Euler Tour Tree 로 O(log² N).
- Holm-Lichtenberg-Thorup: O(log² N) amortized 온라인
- Offline Divide-and-Conquer + Union-Find with rollback: 배치 처리 시 실전 자주 사용
참고
이 글의 용어 (3개)
- 분리 집합 (Disjoint Set, Union-Find)algorithm
- 정의 분리 집합 (Disjoint Set, Union-Find) 은 서로 겹치지 않는 집합들을 관리하며, 다음 두 연산을 거의 상수 시간 (amortized O(α(N)), α는…
- 오일러 투어 테크닉 (Euler Tour Technique)algorithm
- 정의 오일러 투어 테크닉 (ETT, Euler Tour Technique) 은 트리를 DFS 방문 순서로 펼쳐 서브트리 쿼리를 구간 쿼리로 변환하는 정형. 각 노드 u 의 in-…
- Dynamic Tree (Link/Cut Tree, Euler Tour Tree, Top Tree)algorithm
- 정의 Dynamic Tree 는 트리에 간선 추가 (link) / 제거 (cut) 가 섞이는 환경에서 경로 / 서브트리 집계 쿼리 를 O(log N) 에 처리하는 자료구조 가족.…
💬 댓글