---
author: nguyencter
tags: Đồ thị
title: Đồ thị Solution
---

$\Huge\text{Đồ thị Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/file/d/1Avf1-ddrJhpUP830XoK4gzXm3gOvAB55/view?usp=sharing)
📌 Tags: `DFS` `binary search`
✍️ Writer: nguyencter
📋 Content:
[TOC]
:::
## Thuật toán

Đề bài cho tối đa $10^9$ đỉnh nhưng số cạnh tối đa là $10^5$ nên chỉ cần dùng đến tối đa $2*10^5$ đỉnh mà thôi.

Để giải quyết bài toán ta cần nén các đỉnh lại và sử dụng thuật toán chặt nhị phân kết hợp DFS.

Chặt nhị phân để tìm số lần thêm cung tối thiểu để có đường đi từ $s$ đến $t$.

----
Tham khảo code mẫu ở [đây](https://ideone.com/tMQ8BF).