Cho một đồ thị có hướng gồm n đỉnh (đánh số từ 1 đến n) và m cung. Một thành phần liên thông mạnh (SCC) là tập đỉnh tối đại sao cho từ mỗi đỉnh đều có đường đi tới mọi đỉnh khác trong tập và ngược lại.
Hãy đếm số thành phần liên thông mạnh của đồ thị.
Ví dụ: Với 5 đỉnh và các cung 1→2,2→3,3→1,3→4,4→5, các SCC là {1,2,3},{4},{5} nên đáp án là 3.
Dòng đầu chứa hai số nguyên n và m. m dòng tiếp theo, mỗi dòng hai số nguyên u v mô tả cung có hướng từ u tới v.
1≤n≤105, 0≤m≤2⋅105, 1≤u,v≤n. Có thể có cạnh lặp và khuyên.
In ra một số nguyên duy nhất là số thành phần liên thông mạnh.
Ví dụ:
Đầu vào:
5 5
1 2
2 3
3 1
3 4
4 5
Đầu ra:
3
Giải thích:
Đang tải editor...