Ghép cặp công nhân và công việc

Buổi 49 — Matching (Hopcroft-Karp) Buổi 69-70 — Mock Tổng hợp Graphs
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ công nhân (đánh số $1..N$) và $M$ công việc (đánh số $1..M$). Có $K$ cặp $(u, v)$ cho biết công nhân $u$ có thể làm công việc $v$. Mỗi công nhân chỉ làm tối đa $1$ công việc và mỗi công việc chỉ giao cho tối đa $1$ công nhân. Hãy tìm số lượng cặp ghép tối đa.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, M, K$.
  • $K$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$.
Dữ liệu ra

In ra một số nguyên duy nhất là số cặp ghép tối đa.

Ví dụ
Input Output
3 3 4
1 1
1 2
2 1
3 3
3
Giới hạn

$1 \le N, M \le 5 \cdot 10^4$, $0 \le K \le 1.5 \cdot 10^5$.

Draft saved