Đếm số vùng liên thông

View as PDF

Submit solution

Points: 100.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Vùng liên thông trong đồ thị là tập hợp các đỉnh mà từ một đỉnh bất kỳ có đường đi trực tiếp hoặc gián tiếp đến các đỉnh khác trong tập hợp đó. Cho đồ thị vô hướng có N đỉnh, M cạnh. Hãy đếm số lượng vùng liên thông trong đồ thị.

Dữ liệu gồm:

  • Dòng 1: Ghi số nguyên N và M (M, N ≤ 3000).
  • M dòng tiếp theo, mỗi dòng ghi số nguyên dương u và v thể hiện có đường đi giữa hai đỉnh u và v (u, v ≤ N).

Kết quả: Ghi ra số lượng vùng liên thông.

Ví dụ:
INPUT
12 7
1 2
2 5
2 6
6 10
3 4
9 11
9 12
OUTPUT
5

Giải thích:(gồm 3 vùng bên, đỉnh 7, đỉnh 8)


Comments

Please read the guidelines before commenting.



  • -4
    anhtuan2007  commented on Aug. 13, 2022, 9:46 a.m.

    Rất dễ không khó rất xứng đáng với kỳ thi này.