Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOSCOMPS - Connected Components

Cho đồ thị vô hướng N đỉnh. Cho Q truy vấn, mỗi truy vấn thuộc 1 trong 3 loại:

  1. Thêm cạnh (x, y).
  2. Xóa cạnh (x, y).
  3. 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 Output

2 4

1 1 2

3 2 1

2 2 1

3 1 2

10


Được gửi lên bởi:Rain
Ngày:2014-09-20
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOS Round 27

hide comments
2014-09-22 11:06:17 Hướng Thái Dương
bài này k biết có dùng cấu trúc j đặc biệt k nhỉ :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.