Phá hủy từng đỉnh

Buổi 25 — Disjoint Set Union Data-structures Graphs
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho một đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Người ta lần lượt xóa toàn bộ $N$ đỉnh theo một hoán vị $P_1, P_2, \dots, P_N$. Khi xóa một đỉnh, mọi cạnh kề với đỉnh đó cũng bị xóa theo. Hãy cho biết đồ thị còn lại liên thông hay không (in YES nếu các đỉnh còn lại tạo thành đúng 1 thành phần liên thông, ngược lại NO) trước khi thực hiện mỗi lần xóa.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5, 0 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả cạnh nối.
  • Dòng cuối cùng chứa $N$ số nguyên $P_1, P_2, \dots, P_N$ là một hoán vị của $1..N$.
Dữ liệu ra
  • Gồm $N$ dòng, dòng thứ $i$ in ra YES nếu trước khi xóa đỉnh $P_i$, phần đồ thị còn lại liên thông, ngược lại in ra NO.
Ví dụ
Input Output
4 3
1 2
2 3
3 4
3 4 1 2
YES
NO
YES
YES
Giới hạn
  • $1 \le N \le 10^5, 0 \le M \le 2 \cdot 10^5$
Draft saved