Phủ Đỉnh Tối Thiểu
Points
22
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 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
Community Discussion