BOJ 17635: 다리

Link

• https://www.acmicpc.net/problem/17635
• APIO 2019 2번

Tag

• Union-find
• 오프라인 쿼리
• 평방 분할

Time Complexity

• $O(Q \times (\frac {M}{B} lgM + B^2lgB))$ $(B=BucketSize)$

정점 $N(\leq 50,000)$개, 간선 $M(\leq 100,000)$개인 그래프가 주어진다.

1. $i$번 간선의 가중치를 $w$로 변경

2. 정점 $v$에서 가중치가 $w$ 이하인 간선들만 거쳐서 도달할 수 있는 정점의 개수를 출력

두가지 쿼리가 $Q(\leq 100,000)$개 주어진다.

오프라인으로 처리해도 된다.

 

1번 쿼리가 없을 때는, 간선들을 가중치의 내림차순으로 보면서 컴포넌트의 크기를 세주기만 하면 된다.

 

쿼리에 평방 분할을 적용한다. 아래와 같은 방법으로 $B$개의 쿼리를 한번에 처리한다.

1. 1번 쿼리에 영향을 받지 않는 간선들로만 1번 쿼리가 없을 때 처럼 가중치의 내림차순으로 보면서 union-find를 수행한다.

2. 실제로 2번 쿼리에 답해야 할 때는, 해당 쿼리 이전에 주어진 1번 쿼리들을 전부 고려하면서 union-find를 수행한다. 컴포넌트의 크기를 센 뒤에는 다시 롤백한다.

 

union-find에서 롤백이 필요하기 때문에, path compression이 아닌 size compression이나 rank compression을 적용한다. 어차피 컴포넌트의 크기도 구해야 하기 때문에 size compression을 이용한다. 이는 armotized $O(lgN)$에 동작한다.

1. 과정은 $O(MlgM)$시간이 소요된다.

1번 쿼리는 최대 $B$개 있으므로, 2. 과정은 $O(BlgB)$ 시간이 소요된다.

따라서 총 $O(MlgM+B^2lgB)$시간에 한 쿼리 묶음을 처리할 수 있다.

즉 $O(\frac {Q}{B} \times (MlgM + B^2lgB))$ 에 전체 문제를 해결할 수 있다.

$B=\sqrt{Q}$정도로 잡는게 일반적이겠으나, 실제로는 한 쿼리 묶음의 전처리의 오버헤드 때문인지 $B$를 키우는게 더 빠르게 동작한다. 나는 $B=1250$로 했을 때 가장 짧은 수행시간을 보였다.

 

Code