SWERC 2019 K번 문제이다. BOJ 18303번이기도 하다.
rkm0959한테 문제 요약만 들어서 본문을 잘 모른다(…)
Unweighted Directed graph에서 어떤 고정된 정점 $T$에 대해 $u \to T$ 간선이 있고, 이 간선을 사용하지 않으면 $u$에서 $T$로 이동할 수 없는 정점 $u$를 모두 구하는 문제이다. 정점 개수와 간선 개수는 $10^{5}$개 이하.
Solution
뇌정지가 오기 쉬운 문제같다. 풀이도 말로 하기가 어려운듯…
일단 모든 간선의 방향을 뒤집어서 생각하면 시작점이 $T$로 고정된다. 기본적인 세팅.
한 가지 관찰은 $T \to u$ 간선이 $T$에서 $u$로 가는 가장 짧은 경로라는 것이고, 이 간선을 사용하지 않는 경로는 모두 길이가 그보다 strict하게 길다는 것이다.
이제 $T$에서 나가는 간선을 모두 제거하자. $T$에 인접한 모든 $u$들을 시작점으로 하는 multi-source dijkstra 알고리즘을 돌리되, 서로 다른 시작점에서 온 최단 경로 2개를 유지한다. 그냥 BFS로 되는 것 같기도 한데 확신이 없어서 heap 다익스트라를 썼다.
이 때 시작점으로 쓴 $u$들 중 2번째 최단경로가 없는 점들이 우리가 원하는 조건을 만족한다.