---
author: nguyencter
tags: Chase
title: Chase Solution
---

$\Huge\text{Chase Solution}$

-------

:::info
🔗 Links: [Đề bài]()
📌 Tags: `DFS` `dijkstra`
✍️ Writer: nguyencter
📋 Content:
[TOC]
:::
## Thuật toán

Ta thấy trường hợp $Tom$ không bắt được $Jerry$ chỉ xảy ra khi $Tom$ và $Jerry$ không ở chung một thành hành liên thông hoặc $Jerry$ có thể đi vào một chu kì bất kì trước $Tom$.

Vì vậy để giải quyết bài toán ta xét với mỗi đỉnh xem đỉnh này có thuộc chu kì nào hay không.

Tiếp đến với mỗi truy vấn ta chỉ cần kiểm tra xem $Tom$ và $Jerry$ có thuộc cùng một thành phần liên thông hay không và kiểm tra xem có trường hợp nào mà khoảng cách từ $Jerry$ đến một đỉnh thuộc chu kì ngắn hơn khoảng cách của $Tom$ đến đỉnh này hay không. Nếu có thì in ra $0$.

Độ phức tạp là: $O(N^2+2k*N)$

----
Tham khảo code mẫu ở [đây](https://github.com/nguyencter/CODE/blob/main/CHASE.cpp).