Ghép Đôi Trực Tuyến

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

Đề bài

Cho một đồ thị hai phía ban đầu chưa có cạnh nào, gồm $N$ đỉnh phía trái và $M$ đỉnh phía phải.

Có $Q$ truy vấn trực tuyến đến lần lượt. Mỗi truy vấn thêm một cạnh $(u, v)$ vào đồ thị. Ngay sau mỗi truy vấn, hãy in ra kích thước cặp ghép cực đại hiện tại của đồ thị.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên $N, M, Q$ ($1 \le N, M \le 2000$, $1 \le Q \le 10\,000$).
  • $Q$ 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

  • Gồm $Q$ dòng, dòng thứ $i$ là kích thước cặp ghép cực đại sau khi thêm cạnh thứ $i$.

Ví dụ

Input
3 3 5
1 1
2 1
1 2
3 2
2 3
Output
1
1
2
2
3

Giải thích

  • Sau $(1, 1)$: ghép được $1$.
  • Sau $(2, 1)$: vẫn chỉ ghép được $1$.
  • Sau $(1, 2)$: ghép $(1, 2)$ và $(2, 1)$, kích thước là $2$.
  • Sau $(3, 2)$: vẫn là $2$.
  • Sau $(2, 3)$: ghép $(1, 2)$, $(2, 3)$? Không, $(1,1)$, $(3,2)$, $(2,3)$, kích thước là $3$.

Giới hạn

  • $1 \le N, M \le 2000$
  • $1 \le Q \le 10\,000$
  • Thời gian: 3 giây
  • Bộ nhớ: 256 MB
Draft saved