Phủ Đường Đi Trên DAG

Buổi 49 — Matching (Hopcroft-Karp)
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions

Đề bài

Cho một đồ thị có hướng không chu trình (DAG) gồm $N$ đỉnh (đánh số $1$ đến $N$) và $E$ cạnh có hướng.

Hãy tìm số lượng ít nhất các đường đi có hướng rời nhau từng đôi một (mỗi đỉnh thuộc đúng một đường đi, một đường đi có thể chỉ gồm $1$ đỉnh) sao cho hợp của chúng phủ toàn bộ $N$ đỉnh của đồ thị.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên $N, E$ ($1 \le N \le 20\,000$, $0 \le E \le 100\,000$).
  • $E$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$) mô tả cạnh có hướng từ $u$ đến $v$. Dữ liệu đảm bảo đồ thị không có chu trình.

Dữ liệu ra

  • Một số nguyên duy nhất là số đường đi tối thiểu cần dùng.

Ví dụ

Input
4 3
1 2
2 3
2 4
Output
2

Giải thích

Có thể phủ 4 đỉnh bằng 2 đường đi: $1 \to 2 \to 3$ và đường đi chỉ gồm đỉnh $4$.

Giới hạn

  • $1 \le N \le 20\,000$
  • $0 \le E \le 100\,000$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved