Đếm số thành phần liên thông của đồ thị nhỏ
Một đồ thị hiếm khi liền một mảnh. Biết nó tách thành bao nhiêu cụm rời nhau là câu hỏi
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: python-basics, python-lists, python-sets.
Nội dung đề bài
Mô tả bài toán
Một đồ thị hiếm khi liền một mảnh. Biết nó tách thành bao nhiêu cụm rời nhau là câu hỏi đầu tiên khi khảo sát mạng lưới bạn bè, mạng máy tính hay các vùng dữ liệu. Cách làm chuẩn mực rất ngắn: đi qua từng đỉnh, hễ gặp đỉnh chưa thăm thì đó là một thành phần mới, rồi lan ra toàn bộ cụm chứa nó.
Yêu cầu
Viết hàm count_components(adj) trả về số thành phần liên thông của đồ thị vô hướng cho bởi danh sách kề. Đỉnh không có cạnh nào vẫn là một thành phần gồm chính nó.
Quy ước nộp bài
Nộp hàm count_components trong solution.py. Hệ thống gọi hàm trực tiếp bằng tên đối số adj rồi so giá trị trả về; không đọc dữ liệu từ stdin và không in ra stdout.
Input
- adj: danh sách kề gồm n danh sách con, đỉnh đánh số từ 0 đến n - 1; adj[i]
liệt kê các đỉnh kề với đỉnh i.
Output
Một số nguyên là số thành phần liên thông, nằm trong khoảng 0 đến n.
Ràng buộc
- Số đỉnh n từ 0 đến 8; đồ thị vô hướng, không có khuyên và không lặp cạnh.
- Đồ thị rỗng (adj = []) có 0 thành phần; đỉnh cô lập vẫn tính là một thành phần.
- Thời gian cần đạt O(n + m) với m là số cạnh; phải đánh dấu đỉnh đã thăm để không
đếm trùng một cụm.
Ví dụ 1
Input
count_components(adj=[[1, 2], [0], [0], [4], [3]])
Output
2
Ví dụ 2
Input
count_components(adj=[[1], [0, 2], [1], [4], [3], [6], [5]])
Output
3
Giải thích
Với adj = [[1, 2], [0], [0], [4], [3]], ba đỉnh 0, 1, 2 nối với nhau thành một cụm, hai đỉnh 3, 4 thành cụm thứ hai, nên hàm trả về 2.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
