VOSCOMPS - Connected Components
Giới hạn- Thời gian: 2.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho đồ thị vô hướng N đỉnh. Cho Q truy vấn, mỗi truy vấn thuộc 1 trong 3 loại:
- Thêm cạnh (x, y).
- Xóa cạnh (x, y).
- Kiểm tra xem 2 đỉnh x, y có liên thông với nhau không.
Giới hạn :
- 2 <= N <= 10^5
- 1 <= Q <= 10^5
- Trong cùng một thời điểm, có thể có nhiều cạnh giữa 2 đỉnh x, y (đa đồ thị).
- Đối với truy vấn loại 2: nếu có nhiều cạnh (x, y), xóa 1 cạnh bất kì; nếu không có cạnh nào, không làm gì cả.
- Trong 50% tổng số test, 1 <= N, Q <= 5000.
Input:
- Dòng đầu tiên chứa 2 số N, Q.
- Q dòng tiếp theo, mỗi dòng chứa 1 truy vấn có dạng: t x y. Trong đó t = 1, 2 hoặc 3 tương ứng với truy vấn 1, 2 hoặc 3; x, y là 2 đỉnh trên đồ thị (1 <= x, y <= N).
Output:
- Với mỗi truy vấn loại 3, in ra 1 nếu 2 đỉnh x, y liên thông, 0 trong trường hợp ngược lại.
- Các số được in liên tiếp nhau trên cùng một dòng.
Ví dụ:
Input 2 4 1 1 2 3 2 1 2 2 1 3 1 2 Output 10
- Người up: rain1452
- Nguồn bài: VOS Round 27