# Bài 2: KẾ HOẠCH ỨNG PHÓ

### Tóm tắt bài toán:
Cho n vùng và chúng được kết nói với nhau m đường. Yêu cầu tính độ chia cắt của thành phố (tức số thành phần liên thông) sau khi i con đường đầu tiên bị ngập.

### Subtask 1: $n, m ≤ 100$
- Duyệt for từ 1 tới m đánh dấu mỗi con đường và for tiếp từ $1$ tới $m$ để duyệt những con đường chưa bị đánh dấu cho vào vector . Cuối dùng ta dfs để đếm số thành phố liên thông cho những con đường chưa bị đánh dấu.
- Độ phức tạp: $O(m^2 + m^2 * n)$

### Subtask 2: $m = n - 1$ và tồn tại 1 đường đi giữa $i$ và $i + 1$ $(1≤ i < n)$
- Đồ thị được cho là dạng cây với $i$ và $i+1$ liên thông nhau nên với mỗi đường đi từ $1$ -> $m$ số thành phần liên thông là $i+1$ khi $i$ con đường bị loại bỏ.
- Độ phức tạp: $O(m)$

### Subtask 3: $n, m ≤ 10000$
- Đối với dạng bài gộp hoặc kiểm tra các thành phần liên thông thì nên dùng cấu trúc dữ liệu $Dsu$ ($Disjoint$ $Set$ $Union$). Quay lại bài toán ta chỉ cần duyệt ngược từ $m$ -> $1$ dùng $1$ vector lưu lại số thành phần liên thông hiện tại và dùng $Dsu$ gộp 2 đỉnh đó lại. Cuối cùng chỉ cần in ngược lại vector để theo đúng thứ tự mà đề bài cho.

Code Tham Khảo : [**here**](https://ideone.com/EnyoT4)