Đỉnh Bắt Buộc Ghép Đôi

Buổi 49 — Matching (Hopcroft-Karp)
Points
46
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions

Đề 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
Draft saved