Elearning CodePath – CTP Online Judge

Important Link

GRAPH002

🟢 Easy #Graph #BFS/DFS

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho một mạng gồm $N$ nút và $M$ đường truyền hai chiều. Mạng được đảm bảo là **thông suốt** (mọi cặp nút đều truyền tin cho nhau).
* Một tập hợp $K$ nút cung cấp **dịch vụ A**.
* Một tập hợp $L$ nút cung cấp **dịch vụ B**.

Quy tắc: Một nút có thể sử dụng dịch vụ $A$ (hoặc $B$) nếu nó có thể truyền tin tới ít nhất một nút cung cấp dịch vụ $A$ (hoặc $B$). Do mạng thông suốt ban đầu, tất cả các nút đều sử dụng được cả hai dịch vụ.

**Đường truyền quan trọng** là một đường truyền trực tiếp mà nếu nó bị hỏng, có thể làm cho **một số nút** trong mạng **không thể** sử dụng một trong hai dịch vụ (A hoặc B).

Yêu cầu: Xác định số lượng đường truyền quan trọng trong mạng.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `NET.INP`:

* Dòng đầu tiên: Ghi 4 số nguyên $N, M, K, L$.
    * $N$ ($1 \le N \le 10^5$): số nút.
    * $M$ ($1 \le M \le 10^6$): số đường truyền trực tiếp.
    * $K$ ($1 \le K \le N$): số nút cung cấp dịch vụ A.
    * $L$ ($1 \le L \le N$): số nút cung cấp dịch vụ B.
* Dòng thứ hai: Ghi $K$ số là số hiệu các nút cung cấp dịch vụ A.
* Dòng thứ ba: Ghi $L$ số là số hiệu các nút cung cấp dịch vụ B.
* $M$ dòng tiếp theo: Mỗi dòng ghi hai số $p, q$ ($1 \le p, q \le N, p \ne q$) thể hiện một đường truyền trực tiếp nối nút $p$ và nút $q$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `NET.OUT` một số nguyên thể hiện số lượng đường truyền quan trọng trong mạng.

---
### ✨ Ví dụ

| Input (`NET.INP`) | Output (`NET.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `9 10 3 4` `2 4 5` `4 9 8 3` `1 2` `4 1` `2 3` `4 2` `1 5` `5 6` `6 7` `6 8` `7 9` `8 7` | `3` | Nút dịch vụ A: $\{2, 4, 5\}$. Nút dịch vụ B: $\{3, 4, 8, 9\}$. Các đường truyền quan trọng là: $(3, 2), (5, 6), (7, 9)$. |

---
### 🏷  Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 1000, M \le 5000$ | $40\%$ |
| 2 | $N \le 10^5, M \le 10^6$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions