mhy908의 PS 블로그 mhy908의 PS 블로그

문제 상황은 다음과 같다 : 1) DAG에서 어떤 source vertex s가 주어진다. 2) 특정 간선 (혹은 정점) 하나를 삭제했을 때 도달 가능한 정점의 개수를 모든 간선(혹은 정점)에 대해 구하시오. Naive한 방법은 직접 그래프에서 해당 간선 혹은 정점을 삭제한 후 그래프탐색을 통해 O(VE)정도 시간에 해결하는 것인데, 이를 O((N+M)lgN)정도 시간복잡도에 해결할 수 있게 해주는 것이 바로 Dominator Tree이다. 일단, source vertex에서 시작하는 그래프탐색을 통해, 삭제가 없어도 도달이 불가능한 정점들을 전부 삭제시켜두고 시작하자. 이제부터 언급할 정점들은 모두 s에서 어떤 경로를 통해 접근이 가능하다. 몇가지 정의를 짚고 넘어가자. 1) Dominator 어떤 정..