BOJ 1613 - 역사

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

이전 풀이: http://joonas-yoon.blogspot.com/2016/04/1613.html

문제

알고 있는 사건의 전후 관계를 방향성이 있는 간선으로 보면, 서로 다른 두 사건을 유추한다는 것은 어떤 방향으로건 일단 연결이 되어있는가를 물어보는 것이다.

방향 그래프에서 정점 a에서 b로 갈 수 있는 경로가 있는 지 물어보는 문제이다.

a에서 b로 가는 경로가 있으면 앞에 있는 사건이 먼저 일어난 것이므로 -1

b에서 a로 가는 경로가 있다면 1, 경로가 없다면 0을 출력하면 된다.

문제는 이러한 물음이 한두번이 아니라 s번(최대 50,000번) 물어보기 때문에, 경로를 빠르게 찾을 수 있어야한다. 

n이 400으로 작으므로 플로이드 와샬로 각 사건의 연결 관계를 모두 구해둔다면, 쿼리의 대답이 O(1)이므로 시간 내에 해결 가능하다.

코드