Đỉnh Bắt Buộc Ghép Đôi
Points
46
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một đồ thị hai phía gồm $N$ đỉnh phía trái, $M$ đỉnh phía phải và $E$ cạnh nối giữa hai phía.
Một đỉnh được gọi là bắt buộc nếu nó được ghép (thuộc vào cặp ghép) trong mọi cặp ghép cực đại của đồ thị.
Hãy đếm số lượng đỉnh bắt buộc trong đồ thị (tính trên cả $N + M$ đỉnh).
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, E$ ($1 \le N, M \le 50\,000$, $0 \le E \le 150\,000$).
- $E$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u \le N$, $1 \le v \le M$).
Dữ liệu ra
- Một số nguyên duy nhất là số lượng đỉnh bắt buộc.
Ví dụ
Input
2 2 2
1 1
2 1
Output
1
Giải thích
Cặp ghép cực đại có kích thước $1$: hoặc $(1, 1)$ hoặc $(2, 1)$. Chỉ có đỉnh $1$ ở phía phải luôn được ghép trong mọi cặp ghép cực đại.
Giới hạn
- $1 \le N, M \le 50\,000$
- $0 \le E \le 150\,000$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion