[BOJ] 8452번: 그래프와 쿼리

https://www.acmicpc.net/problem/8452

꽤 오래 고민을 했는데도 해답을 찾지 못해서 풀이를 찾아봤습니다. 풀이에 적힌 방법은 생각을 해봤던 방법이었는데 시간복잡도가 가늠이 잘 안가 포기했던 방법이었습니다.

일단 간선을 제거하는 문제로 생각하지 말고, 간선을 추가하는 문제로 생각을 합니다. 이는 쿼리를 역순으로 생각하면 됩니다. 이제 간선을 추가하면서 최단 경로의 갱신이 필요할 경우 BFS를 돌려주면 되는데, 저는 여기서 갱신이 최대 Q번 발생하므로 $O(Q(V+E))$f로 시간초과가 발생할 것이라고 생각했습니다.

그런데 각 노드에 대해 생각해보면, 각 노드에서 갱신은 최대 V번 발생하므로 각 노드의 관점에서 $O(V*out degree)$만큼만 다른 노드를 확인하면 되고 모든 노드에 대해 생각하면 시간복잡도가 $O(VE)$가 됩니다.

https://github.com/blisstoner/BOJ/blob/master/8452.cpp