---
# System prepended metadata

title: SPECONE Solution
tags: [CP]

---

---
author: nguyencter
tags: SPECONE 
title: SPECONE Solution
---

$\Huge\text{SPECONE Solution}$

-------

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

-----

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

Trong trường học có $N$ học sinh và $S$ học sinh đặc biệt, được biết với mỗi học sinh chưa là đặc biệt mà trao đổi tin nhắn với ít nhất $K$ người đã là đặc biệt thì học sinh đó sẽ trở thành người đặc biệt.

**Yêu cầu:** cho $M$ đoạn tin nhắn trao đổi giữa 2 học sinh, hãy xác định xem nhiều nhất có thể có bao nhiêu học sinh trở thành người đặc biệt và cụ thể là những người nào.

-----

## Thuật toán

Ta xem mỗi người này là một đỉnh của đồ thị để BFS.

Dùng danh sách kề để lưu lại các lần trao đổi tin nhắn.

Dùng một $map<string,int> cnt$ để lưu lại số lần trao đổi tin nhắn với người đặc biệt của mỗi người.

Đặt $S$ đỉnh đặc biệt ban đầu vào hàng đợi 2 đầu để tiến hành BFS.

- Gọi $v$ là đỉnh kề với đỉnh đặc biệt đang được xét
- Với mọi $v$ ta cộng $cnt[v]$ lên một đơn vị.
- Kiểm tra nếu $cnt[v]=k$ thì đỉnh $v$ này là một đỉnh đặc biệt mới và lưu đỉnh này vào hàng đợi. 

Lưu các đỉnh đặc biệt lại và in ra kết quả.

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