---
author: little
tags: Đua xe đạp
title: Đua xe đạp Solution
---

$\Huge\text{Đua xe đạp Solution}$

-------

:::info
📌 Tags: `dfs` `dp`
✍️ Writer: little
📋 Content:
[TOC]
:::

-----

## Thuật toán

Ta có thể thấy, những đỉnh mà không đến được từ đỉnh $1$ và những đỉnh mà từ nó ta không thể đi đến được đỉnh $2$ thì sẽ không xuất hiện trên đường đi từ đỉnh $1$ đến đỉnh $2$. Vì vậy, ta có thể loại bỏ các đỉnh đó ra khỏi đồ thị hiện tại.

Như vậy, số lượng đường đi là $inf$ khi và chỉ khi tồn tại một chu trình bất kì trên đồ thị mới.

Trường hợp không có chu trình trên đồ thị mới, thì đồ thị mới của ta sẽ là một $DAG$. Vì vậy ta có thể dễ dàng sử dụng $dp$ để đếm số lượng đường đi từ $1$ đến $2$.

----

Tham khảo code ở [đây](https://ideone.com/W1Y97B)