#869. BOXES - Hộp đựng tiền

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Bill là một lập trình viên hết sức tiết kiệm. Tiềm kiếm được bằng việc thiết kế Web được anh chia ra cất giữ trong n hộp (1 ≤ n ≤ 10^5) . Các hộp được đánh số từ 1 đến n . Mỗi hộp có một ổ khóa riêng và chìa của mỗi ổ khóa được bỏ vào một hộp nào đó. Muốn lấy tiền ra thì hoặc phải có chìa khóa hoặc phải đập vỡ hộp. Bị hớp hồn bởi một siêu máy tính mới, Bill quyết định lấy hết tiền tiết kiệm trong các hộp để mua. Anh không muốn phải đập hết các hộp. Điều may mắn là Bill còn giữ được mẩu tài liệu cho biết chìa khóa của mỗi hộp được bỏ vào hộp nào. Vì vậy anh chỉ cần đập vỡ một số hộp. Bill muốn mở hết các hộp với số lượng hộp bị đập vỡ là ít nhất. Ví dụ, nếu chìa khóa hộp 2 được bỏ vào hộp 1 , các chìa khóa hộp 1 3 được bỏ vào hộp 2 , chìa khóa hộp 4 được bỏ vào ngay trong hộp 4 . Khi đó Bill chỉ cần phải đập vỡ 2 hộp: hộp 4 và một hộp nữa, chẳng hạn hộp 1 .

Yêu cầu: Cho biết n và nơi lưu mỗi chìa khóa. Hãy xác định số hộp ít nhất phải đập.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên n ;
  • n dòng tiếp theo, dòng thứ i chứa một số nguyên xác định hộp chứa chìa khóa của hộp i .

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là số hộp phải đập ít nhất tìm được.

Ví dụ:

Dữ liệu vào:

4
2
1
2
4

Dữ liệu ra:

2

Giới hạn:

  • 50\% số điểm tương ứng 50\% số test có n≤1000 .