Nguồn:
Mr Kiên
Cho một
đồ thị vô hương gồm N đỉnh và M cạnh, có Q truy vấn, mỗi truy vấn
có dạng x, y. Yêu cầu kiểm tra xem x và y có cũng thuộc một thành
phần liên thông hay không (từ x có thể đi tới y thông qua một số cạnh
hay không).
Dữ liệu vào: Từ tệp văn bản CONNECT.INP
+ Dòng
đầu tiên chứa ba số nguyên dương N, M, Q lần lượt là số đỉnh, số
cạnh và số lượng truy vấn (1≤N, M≤105, Q≤106+1
)
+ M
dòng tiếp theo, mỗi dòng gồm hai số nguyên dương x, y, chỉ một cạnh nối
hai đỉnh x và y.
+ Q
dòng tiếp theo, mỗi dòng là một truy vấn có dạng x y.
Dữ liệu ra: Ghi vào tệp văn bản CONNECT.OUT
Với mỗi
truy vấn dạng x y, in ra “YES” nếu x và y là hai đỉnh cùng thuộc
một thành phần liên thông, in ra “NO” trong trường hợp ngược lại.
|
CONNECT.INP
|
CONNECT.OUT
|
|
3 1 3
1 2
2 1
1 3
3 2
|
YES
NO
NO
|
