#789. Truyền tin (NEWS)

Quách Gia của chúng ta đang sống rất tiêu dao tự tại dưới trướng Tào Tháo, nhưng một ngày nọ Tào Tháo giao cho ông một nhiệm vụ: Trong thành Kiến Nghiệp có gián điệp của Viên Thiệu, được đánh số từ đến . Giữa họ tồn tại một mối quan hệ truyền tin, cụ thể nếu , thì gián điệp có thể truyền tin trực tiếp cho gián điệp .

Bây giờ Tào Tháo muốn tung một tin giả và cần truyền đạt cho tất cả các gián điệp. Quách Gia cần truyền tin cho ít gián điệp nhất có thể sao cho tất cả các gián điệp đều biết tin này. Hỏi ít nhất phải truyền cho bao nhiêu gián điệp ban đầu?

Dữ liệu:

• Dòng đầu tiên chứa số .
• Từ dòng thứ 2 đến dòng là một ma trận (nếu dòng cột là , thì gián điệp có thể truyền tin trực tiếp cho gián điệp ; nếu là , thì không thể).

Kết quả:

• Một dòng duy nhất chứa số lượng gián điệp ít nhất mà Quách Gia cần truyền tin ban đầu.

Ví dụ:

Dữ liệu:

8
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0

Kết quả:

2

Giới hạn: .