---
author: little
tags: Đường truyền quan trọng
title: Đường truyền quan trọng Solution
---

$\Huge\text{Đường truyền quan trọng Solution}$

-------

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

-----

## Thuật toán

Ta có nhận xét : một đường truyền chỉ có thể là đường truyền quan trọng nếu khi xóa bỏ đường truyền đó thì hệ thống mạng bị chi rẽ thành $2$ phần. Hay nói cách khác, một đường truyền chỉ có thể là đường truyền quan trọng nếu nó là cạnh cầu của đồ thị.

- Trong khi tìm cạnh cầu thì ta lưu lại cây $Dfs$ đó luôn.
- Gọi :
- $dp1_u$ là số lượng đỉnh cung cấp dịch vụ $A$ trong cây con gốc $u$.
- $dp2_u$ là số lượng đỉnh cung cấp dịch vụ $B$ trong cây con gốc $u$.
- Với mỗi cạnh cầu $(u,v)$ ($v$ là đỉnh nằm thấp hơn $u$ trong cây $Dfs$) trong đồ thị đã cho, thì nó chỉ có thể là đường truyền quan trọng nếu như thỏa mãn một trong các điều kiện sau:
- $dp1_v = 0$ (thành phần liên thông chứa đỉnh $v$ không có dịch vụ $A$).
- $dp1_v = K$ (thành phần liên thông chứa đỉnh $u$ không có dịch vụ $A$).
- $dp2_v = 0$ (thành phần liên thông chứa đỉnh $v$ không có dịch vụ $B$).
- $dp2_v = L$ (thành phần liên thông chứa đỉnh $u$ không có dịch vụ $B$).

Độ phức tạp bài toán: $O(n + m)$.

----

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