---
author: nguyencter
tags: GRAPH
title: GRAPH Solution
---

$\Huge\text{GRAPH Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/file/d/1SaQMS9mlVtDkvbpsMq5cqY4DfI04vOZw/view?usp=sharing)
📌 Tags: `binary search`
✍️ Writer: nguyencter
📋 Content:
[TOC]
:::

-----

## Giới Thiệu Đề Bài

Một cách mô tả đồ thị là liệt kê bậc của các đỉnh. Bậc của một đỉnh là số cạnh xuất phát từ đỉnh đó. Nếu có $n$ đỉnh thì ta chỉ cần dùng $n$ số nguyên. Ở đây ta chỉ xét các đồ thị đơn, giữa 2 đỉnh không có quá một cạnh và không có cạnh nối một đỉnh với chính nó.

**Yêu cầu:** Cho $n$ số nguyên. Hãy xác định có tồn tại hay không một đồ thị nhận các số đã cho làm bậc của đỉnh.

-----

## Thuật toán

Ta thấy cách dựng đồ thị tối ưu nhất là lấy đỉnh có bậc lớn nhất nối với các đỉnh có bậc lần lượt từ lớn tới bé nên mảng $a$ ta sắp xếp theo thứ tự không tăng.

Với mỗi đỉnh $i$ có bậc $a[i]$ ta có điều kiện để tồn tại đỉnh $i$ là:

- Tổng $a[1],...,a[n]$ chẵn.
- Tổng $a[1],...,a[i]<=i*(i-1)+$tổng$(min(i,a[i+1]),...,min(i,a[n]))$.

Để giảm số lượng thao tác ta sử dụng mảng cộng dồn để tính tổng $a[1]$ đến $a[i]$.

Vì mảng $a$ đã được sắp xếp theo thứ tự không tăng nên ta có thể sử dụng chặt nhị phân để tính tổng$(min(i,a[i+1]),...,min(i,a[n]))$.

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

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