Connected Components

View as PDF

Submit solution

Points: 1.60 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VOS Round 27
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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.

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 \le x~, ~y \le 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.

Giới hạn

  • ~2 \le N \le 10^{5}~
  • ~1 \le Q \le 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 \le N~, ~Q \le 5000~.

Sample Input

2 4
1 1 2
3 2 1
2 2 1
3 1 2

Sample Output

10

Comments

Please read the guidelines before commenting.


There are no comments at the moment.