---
author: nguyencter
tags: Newroads
title: Newroads Solution
---

$\Huge\text{Newroads Solution}$

-------

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

**Nhận xét**: Hai đỉnh $A$ và $B$ là $2$ thành phố thân thiện khi $2$ đỉnh này cùng nằm trong $1$ thành phần liên thông mạnh.

Vì vậy để giải quyết bài toán ta cần tìm số lượng đỉnh và cạnh trong mỗi thành phần liên thông mạnh rồi lấy số lượng cạnh tối đa trừ đi số cạnh đã có.

Công thức tính số lượng cạnh tối đa của $1$ thành phần liên thông mạnh: $(S-1)*S$,($S$ là số lượng đỉnh).

Độ phức tạp là: $O(N*M)$.

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