Đếm đỉnh có thể đến được

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một đồ thị có hướng không chu trình (DAG) gồm $n$ đỉnh và $m$ cạnh. Hãy tính với mỗi đỉnh số lượng đỉnh có thể đến được từ đỉnh đó (bao gồm chính nó).

Dữ liệu vào

Dòng đầu: hai số nguyên $n$ và $m$ ( $1 \leq n \leq 5 \cdot 10^{4}$ , $1 \leq m \leq 10^{5}$ ).
$m$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ và $b$ ( $a \neq b$ ) mô tả một cạnh có hướng từ $a$ đến $b$ .

Dữ liệu ra

In ra $n$ số nguyên trên một dòng, số thứ $i$ là số đỉnh có thể đến được từ đỉnh $i$ .

Ràng buộc

$1 \leq n \leq 5 \cdot 10^{4}$
$1 \leq m \leq 10^{5}$
Đồ thị là DAG (không có chu trình).

Ví dụ

Input	Output	Giải thích
5 6 1 2 1 3 1 4 2 3 3 5 4 5	5 3 2 2 1	Từ đỉnh 1 có thể đến tất cả 5 đỉnh; từ đỉnh 2 đến được {2,3,5}; từ đỉnh 3 đến được {3,5}; từ đỉnh 4 đến được {4,5}; từ đỉnh 5 chỉ đến được chính nó.
6 10 1 2 2 3 2 3 2 4 1 4 2 4 1 5 4 5 5 6 1 6	6 5 1 3 2 1

Bình luận

Không có bình luận tại thời điểm này.