문제 링크
- http://icpc.me/7907
사용 알고리즘
- 위상정렬
시간복잡도
- $O(N+M+K)$
풀이
문제에서 두 가지를 관찰해야합니다.
- “두 점을 모두 지나는 경로가 존재하지 않는다”는 것은 “한 점을 지나면 다른 한 점을 지나지 못한다”는 것과 동치입니다.
- 문제에서 주는 그래프는 DAG이기 때문에, A -> B로 가는 경로가 있으면 B -> A로 가는 경로는 없습니다.
위의 두 가지 성질을 잘 이용해 문제를 풀어봅시다.
DAG는 위상정렬을 할 수 있고, 그래프의 형태에 따라 위상정렬의 결과가 여러가지가 나올 수 있습니다.
A와 B를 모두 지나는 경로가 존재하고 A를 지난 후에 B를 지난다고 하면, 어떻게 위상정렬을 하더라도 항상 A가 B보다 먼저 나오게 됩니다. 마찬가지로 B를 지난 후에 A를 지난다고 하면, 어떻게 위상정렬을 하더라도 항상 B가 A보다 먼저 나오게 됩니다.
반대로, A와 B를 모두 지나는 경로가 없는 경우에는 위상정렬을 어떻게 하는지에 따라 A가 먼저 나올 수도 있고, B가 먼저 나올 수도 있습니다.
여기까지 관찰을 했으면, 최대한 다른 결과가 나오도록 위상정렬을 해서 두 정점의 전후 관계를 살피는 것을 구현하면 된다는 것을 알 수 있습니다.
간선의 방향을 보면 아래쪽으로 이동하는 간선과 오른쪽으로 이동하는 간선, 총 두 가지만 존재합니다. 첫 번째 위상정렬을 최대한 오른쪽으로 먼저 가도록 dfs를 돌려 위상정렬을 해주고, 두 번째 위상정렬은 최대한 왼쪽으로 먼저 가도록 dfs를 돌려 위상정렬을 해주면 됩니다.
두 가지 결과에 대해 각 정점이 몇 번째인지 전처리를 해놓으면 각 쿼리마다 상수 시간에 답을 구할 수 있습니다.
위상정렬로 전처리를 하는데 $O(N+M)$이 걸리고, $O(K)$개의 쿼리를 각각 상수시간에 처리하므로 총 시간 복잡도는 $O(N+M+K)$입니다.
구현은 5분 이내로 할 수 있을 정도로 매우 간단합니다.