--- 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).