Ghép Đôi Tối Đa
Points
15
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 (đá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
Community Discussion