문제 링크
- http://icpc.me/8496
문제 출처
- 2009 POI ONTAK 51번
사용 알고리즘
- SCC
- Union-Find
- PBS
시간복잡도
- $O(M log M)$
풀이
모 교육에서 풀이를 들은 문제입니다.
문제를 간단히 요약하면, $N$개의 정점과 $M$개의 간선으로 이루어진 그래프에서 간선을 제거하는 쿼리가 Q개 주어질 때, 각 쿼리를 처리한 후의 그래프에서 indegree가 0인 SCC의 개수를 구하는 문제입니다.
간선을 제거하는 쿼리는 “당연히” 순서를 뒤집어 간선을 추가하는 쿼리로 바꿔주고 시작합시다.
$Q = M$으로 가정하고 풀어도 됩니다. 쿼리로 주어지지 않은 간선은 적당히 처리해주면 됩니다.
Naive한 풀이는 $O(M^2)$으로, 당연히 TLE가 납니다. (많이 어렵고) 효율적인 풀이를 알아봅시다.
각 간선$(u, v)$에 대해서, $u$, $v$가 같은 SCC에 속해지는 시점을 구하는 방법을 먼저 생각해봅시다.
$u$, $v$가 이미 같은 간선에 속해있다면 그 시점은 간선이 추가되는 시점이고, 그렇지 않다면 어떻게 간선들이 잘 돌아서 $v$에서 $u$로 가는 경로가 만들어지는 시점입니다.
이것을 계산하는 것은 Parallel Binary Search(병렬 이분 탐색, PBS) 느낌으로 처리할 수 있습니다.
solve(L, R, Edge) = Edge들이 시점 $[L, R]$ 구간 안에서 같은 SCC로 속하게 될 때, 정확히 어느 시점에 SCC로 속하는 지 구하는 함수
라고 정의를 하고 분할 정복을 합시다.
$M = \lfloor \frac {L+R}{2} \rfloor$ 인 M을 잡고, Edge들 중 시점 $[1, M]$ 구간에 속하는 간선들로만 SCC를 만들어줍시다.
Edge에 있는 각 간선 $(u, v)$에 대해 $u$와 $v$가 같은 SCC에 속해있다면 L_Edgd에, 그렇지 않다면 R_Edge에 넣고 solve(L, M, L_Edge), solve(M+1, R, R_Edge) 처럼 분할 정복을 해주면 됩니다.
분할 정복 과정에서 $L = R$ 인 상황이 온다면, Edge에 있는 간선들이 정확히 L 시점에 같은 SCC로 속하게 된다는 것을 의미합니다. 이런 base case에서 처리할 것을 알아봅시다.
base case까지 내려간 상황이면 각 간선이 정확히 어느 시점에 SCC에 속하게 되는 지 알고 있는 상황입니다. 이 시점에서 간선의 양 끝 정점을 union-find로 합쳐줍시다. 이런 방식으로 SCC를 관리해줄 수 있습니다. 정점이 합쳐질 때 indegree를 더하고 수명이 끝나면 indegree를 제거하는 방식으로 컴포넌트의 indegree를 계산할 수 있고, indegree가 0인 컴포넌트의 개수도 함께 관리해줄 수 있습니다.
이렇게 하면 $O(M log M)$에 문제를 해결할 수 있습니다.