---
author: nguyencter
tags: Reform
title: Reform Solution
---

$\Huge\text{Reform Solution}$

-------

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

**Nhận xét**: Ta chỉ có thể thêm $1$ cạnh vào đồ thị nên số thành phần liên thông tối đa chỉ là $2$. Ta chia bài toán thành $2$ trường hợp:

1. Đồ thị gồm $2$ thành phần liên thông:
- Giả sử $2$ thành phần liên thông của đồ thị có số đỉnh lần lượt là $C_1$ và $C_2$ $(C_1+C_2=n)$.
- Do đồ thị có $2$ thành phần liên thông, ta cần $1$ cạnh nối $2$ thành phần liên thông này với nhau và số cách nối là $C_1*C_2$. Đối với cạnh cần bỏ đi, ta có một nhận xét là cạnh này không được là cầu (bởi nếu bỏ đi cầu, số thành phần liên thông sẽ tăng lên). Do đó, số cách tính được trong trường hợp này là $(m-c)*C_1*C_2$ (với $c$ là số cầu của đồ thị).
2. Đồ thị chỉ có $1$ thành phần liên thông:
- Xét cạnh bị bỏ đi, ta có $2$ trường hợp:
- TH 1: Cạnh bỏ đi không là cầu: Đồ thị vẫn liên thông sau khi bỏ cạnh. Do đó, ta có thể thêm bất kì cạnh nào khác $m$ cạnh lúc đầu. Ta có $n*(n-1)/2-m$ cách thêm cạnh mới.
- TH 2: Cạnh bỏ đi là cầu: Đồ thị sẽ bị chia thành $2$ thành phần liên thông. Do đó, cạnh thêm vào phải nối $2$ thành phần liên thông đó lại. Gọi $C_1$ và $C_2$ lần lượt là số đỉnh của $2$ thành phần liên thông đó. Ta có $C_1*C_2-1$ cách thêm (không tính cạnh vừa bỏ đi).

Cuối cùng chỉ việc tính tổng số cách trong từng trường hợp.

Độ phức tạp là: $O(n+m)$.

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