[BOJ] 1613번: 역사

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

$a$가 $b$ 보다 먼저 발생한 사건이면 $adj[a]$에 $b$를 추가합니다. 그리고 1, 2, ... , $N$에서 flood fill을 돌리면 각 사건들에 대해 나보다 먼저 발생한 사건의 목록을 알 수 있고 이를 미리 $state[i][j]$에 저장해두면 $O(NK+S)$에 해결할 수 있습니다.

만약 $N$이 더 컸다면 LCA를 이용해 $O((K+S)lgN)$에 해결할 수 있었을 것입니다.

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