Phủ Đỉnh Tối Thiểu

Buổi 49 — Matching (Hopcroft-Karp)
Points
22
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 tập đỉnh $S$ được gọi là tập phủ đỉnh (Vertex Cover) nếu mọi cạnh $(u, v)$ của đồ thị đều có ít nhất một đầu mút thuộc $S$ ($u \in S$ hoặc $v \in S$).

Theo định lý König, trên đồ thị hai phía, kích thước tập phủ đỉnh tối thiểu bằng kích thước cặp ghép cực đại. Hãy tìm kích thước nhỏ nhất của một tập phủ đỉ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à kích thước nhỏ nhất của tập phủ đỉnh.

Ví dụ

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

Giải thích

Chọn đỉnh $1$ ở phía trái và đỉnh $2$ ở phía phải. Mọi cạnh đều có ít nhất một đầu mút nằm trong tập ${L_1, R_2}$. Không có tập phủ đỉnh nào kích thước $1$.

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