Offline Dynamic Connectivity algorithm
오프라인 다이나믹 커넥티비티 알고리즘을 알아보자. Offline Dynamic Connectivity 는 간선 추가, 삭제를 오프라인으로 처리하는 문제에 쓰인다. 대표적으로 BOJ의 16911 = 16912 = 15316 < 12876 < 15946 순으로 문제가 어렵다. (16911,16912,15316 이 3개중 하나만 풀어도 나머지 2개는 꽁짜..) 여러가지 방법이 있겠지만 저는 분할 정복을 사용했습니다. (사실 1가지임 ㅋ) 일단 간선의 라이프 타임을 저장해 둡니다. (나타난 시간 ~ 사라진 시간) 생기고 지워진 적이 없다면 맨 마지막 시간으로 해둡니다. (나타난 시간 ~ 마지막 시간) 이제 분할정복을 해줄텐데 solve(l,r,Edge set) l~r : 간선 라이프 타임이 l~r 이고 m = ..
카테고리 없음
2020. 4. 10. 01:56