Đếm thành phần liên thông

Trung bình

đồ thịDSU / BFS5 test · 3 giây

Có n thành phố đánh số 1..n và m con đường hai chiều. Hai thành phố thuộc cùng một vùng nếu đi được tới nhau. Đếm số vùng.

Dữ liệu vào

Dòng 1: n m (1 ≤ n ≤ 2·10⁵, 0 ≤ m ≤ 2·10⁵).

m dòng: u v (có thể có cạnh lặp hoặc u = v).

Số vùng liên thông.

Input

Output

Input

3 0

Output

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.