## Editorial: Kết nối chơi game - POTW 2

#### I. Tóm tắt đề:

Cho $N$ học sinh, $M$ tựa game và $Q$ đường liên kết được lắp đặt từ phút thứ $1$ tới phút thứ $Q$, trong mỗi phút, hai máy tính $U_i$ và $V_i$ sẽ được kết nối (ở đây mạng lưới liên kết được coi là đồ thị vô hướng), tựa game $X$ sẽ được chơi khi tất cả các máy tính của thành viên chơi game trên **liên thông với nhau**. In ra $M$ với dòng thứ $i$ $(1\leq i\leq m)$ là thời gian bắt đầu chơi game thứ $i$ kể từ khi bắt đầu (in ra $-1$ nếu game thứ $i$ không thể liên thông).

#### II. Ý tưởng của bài

Ta nhận thấy, để kiểm tra các máy tính chơi cùng một game đã liên thông hay chưa ta có thể dùng ***Disjoin Set Union*** (tìm hiểu ở [đây](https://vnoi.info/wiki/algo/data-structures/disjoint-set-union.md)).

Cụ thể, trong phút thứ $i$, ta đọc $U_i$ và $V_i$ tương ứng rồi dùng phép *Join* của $DSU$ để liên kết hai thành phần liên thông của $U_i$ và $V_i$ với nhau rồi kiểm tra nhờ đường liên kết này, các game nào vừa được liên thông hoàn toàn.

Vậy, chúng ta làm như thế nào để kết hợp hai TPLT với nhau, theo một cách đơn giản, ta có thể lưu một TPLT dưới dạng một ***map*** đếm số lượng người chơi một game nào đó rồi so sánh với số lượng người chơi cần có để game bắt đầu, nếu thỏa mãn và game chưa được chơi trước đó, ta cập nhật thời gian bắt đầu cho game đó là $i$ luôn.

Ngoài ra, khi *merge* hai map với nhau, thay vì duyệt hết mọi thể loại game, ta chỉ cần dùng thuật ***Small to large*** để gộp nhanh hai map trong $O(n log (n + m))$

Lưu ý nhỏ để kết quả chính xác thì ta cần duyệt các game, game nào chỉ có $1$ người chơi thì ta cập nhật luôn kết quả là $0$ vì người chơi này không cần liên kết với ai cả.

[Code Submission AC](https://ideone.com/zYtM9u).