Ghép Đôi Tối Đa

Buổi 49 — Matching (Hopcroft-Karp)
Points
15
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 (đánh số từ $1$ đến $N$), $M$ đỉnh ở phía phải (đánh số từ $1$ đến $M$) và $E$ cạnh nối giữa một đỉnh phía trái và một đỉnh phía phải.

Hãy tìm kích thước của cặp ghép cực đại (Maximum Bipartite Matching) — tức số lượng cạnh nhiều nhất có thể chọn sao cho không có hai cạnh nào chung đỉ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$) mô tả một cạnh nối đỉnh $u$ phía trái với đỉnh $v$ phía phải.

Dữ liệu ra

  • Một số nguyên duy nhất là kích thước cặp ghép cực đại.

Ví dụ

Input
3 3 4
1 1
1 2
2 2
3 3
Output
3

Giải thích

Có thể chọn 3 cạnh: $(1, 1)$, $(2, 2)$ và $(3, 3)$.

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