Các thành phần liên thông mạnh

Time limit: 1.0s , Memory limit: 500M , Points: 25 (partial)

Cho đồ thị có hướng $G = (V, E)$ ~G = (V, E)~ với $|V| = n$ ~|V| = n~ là tập đỉnh, $|E| = m$ ~|E| = m~ là tập cạnh. Một đồ thị con $G'$ ~G'~ của $G$ ~G~ được gọi là một thành phần liên thông mạnh nếu hai tính chất sau thỏa mãn:

Tính chất 1: hoặc $G'$ ~G'~ chỉ có $1$ ~1~ đỉnh, hoặc với hai đỉnh bất kỳ $v_i, v_j$ ~v_i, v_j~ của $G'$ ~G'~ luôn tồn tại đường đi giữa chúng.
Tính chất 2: việc thêm vào $G'$ ~G'~ một đỉnh bất kỳ sẽ làm hỏng tính chất $1$ ~1~.

Xét đồ thị như hình vẽ sau ta sẽ có $2$ ~2~ thành phần liên thông mạnh, gồm: $\{4\}$ ~\{4\}~ và $\{1,2,3\}$ ~\{1,2,3\}~.

Bài toán hôm nay Trung đặt ra cho các bạn là đếm số thành phần liên thông mạnh của một đồ thị $G$ ~G~ cho trước.

Input

Dòng thứ nhất chứa hai số nguyên $n, m$ ~n, m~ là số đỉnh và cung của đồ thị thỏa $1 \le n \le 1000, 1\le m \le 5000$ ~1 \le n \le 1000, 1\le m \le 5000~.

$m$ ~m~ dòng tiếp theo mỗi dòng chứa hai số $v_i, v_j$ ~v_i, v_j~ thể hiện cung nối từ $v_i$ ~v_i~ đến $v_j$ ~v_j~.

Output

In ra số thành phần liên thông mạnh cần đếm.

Samples

Sample Input 1

Sample Output 1

Comments

0

thekingchau commented on Feb. 29, 2024, 1:26 p.m.

liệu có thể giúp đàn em thơ ngây thiếu kiến thức làm bài này được không ạ :)

Link

0

thekingchau commented on Feb. 29, 2024, 1:25 p.m.

các tiền bối :)

Link