Daily 18/08/2023: [1615. Maximal Network Rank](https://leetcode.com/problems/maximal-network-rank/description/)

# 1. Tóm tắt đề bài

Cho một đồ thị vô hướng có $N$ đỉnh và $M$ cạnh. Tìm một cặp đỉnh mà có nhiều cạnh nhất trên đồ thị, trực tiếp nối một trong hai đỉnh này. Nếu có một cạnh nối trực tiếp cả hai đỉnh trong cặp, thì cũng chỉ tính là một cạnh.

##### Giới hạn

$1 \le N \le 100$.

$1 \le M \le \frac{N * (N + 1)}{2}$.

Mỗi cặp đỉnh chỉ có duy nhất một cạnh.

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(N ^ 2 + M)$**

Ta định nghĩa $deg(i)$ là số cạnh nối trực tiếp với đỉnh $i$.

Xét một cặp đỉnh $(i, j)$, nếu ta chỉ đơn thuần tính $deg(i) + deg(j)$ để tính số cạnh trong đồ thị nối trực tiếp đến cặp đỉnh này, thì các cạnh nối trực tiếp $i$ với $j$ sẽ luôn bị tính hai lần. Vì vậy, ta định nghĩa $edgeCount(i, j)$ là số cạnh nối trực tiếp $i$ và $j$, thì công thức đúng sẽ là $deg(i) + deg(j) - edgeCount(i, j)$.

# 3. Lời giải chi tiết

- Các bạn có thể lưu các giá trị $deg$ dưới dạng mảng một chiều $N$, và $edgeCount$ dưới dạng mảng hai chiều $N * N$.
- Sau đó, ta duyệt một vòng qua $roads$ để tính các giá trị $deg$ cũng như $edgeCount$.
- Cuối cùng, ta duyệt qua từng cặp đỉnh một, và tính công thức trên, và tìm giá trị của cặp đỉnh tối ưu nhất.

### Độ phức tạp thuật toán

Thời gian: $O(N * N + M)$

Bộ nhớ mở rộng: $O(N * N)$, do có $edgeCount$

# 4. Kết luận & Gợi ý mở rộng

Cách của mình giải quyết cả bài toán mà không có giới hạn cuối cùng, khi các cạnh nối cùng một cặp thành phố cũng đã được tính vào $edgeCount$.

Bài này sử dụng kiến thức cơ bản nhất của Graph. Các bạn có thể xem **[các cách biểu diễn Graph](https://www.geeksforgeeks.org/graph-and-its-representations/?ref=lbp)** ở link mình đính kèm.

Bài này sử dụng chút tư duy bao hàm-loại trừ. Đối với các bạn hăng hái học hỏi: [Số học 7 - Bao hàm - Loại trừ (Inclusion-Exclusion)](https://vnoi.info/wiki/translate/he/Number-Theory-7.md).

Một số bài tập mình gợi ý thêm:

[785. Is Graph Bipartite?](https://leetcode.com/problems/is-graph-bipartite/)
[1319. Number of Operations to Make Network Connected](https://leetcode.com/problems/number-of-operations-to-make-network-connected/)
[2421. Number of Good Paths](https://leetcode.com/problems/number-of-good-paths/description/)