Đếm thành phần liên thông
Bài học 13 trên 14 trong khóa học Đồ thị, chuỗi cấu trúc dữ liệu #9 của Coddy.
Thành phần liên thông là một tập hợp đỉnh tối đại, trong đó mọi cặp đỉnh đều có đường đi nối chúng. Đồ thị không có cạnh có số thành phần bằng số đỉnh; đồ thị liên thông hoàn toàn chỉ có đúng một thành phần.
Để đếm các thành phần, hãy duyệt qua tất cả các đỉnh. Khi gặp một đỉnh chưa được thăm, đó là một thành phần mới: tăng bộ đếm, rồi chạy BFS hoặc DFS từ đỉnh đó để đánh dấu tất cả các đỉnh có thể đi đến là đã được thăm. Tiếp tục với đỉnh chưa được thăm tiếp theo.
Thử thách này cung cấp cho bạn CẢ danh sách đỉnh VÀ các cạnh, vì các đỉnh cô lập (không có cạnh) vẫn được tính là một thành phần riêng và chúng ta cần biết chúng tồn tại.
Thử thách
DễViết một hàm countConnectedComponents nhận mảng số nguyên 2D adjacency và mảng số nguyên vertices, rồi trả về số thành phần liên thông trong đồ thị.
Dựng đồ thị: trước tiên gọi addVertex cho mọi khóa trong vertices (để các đỉnh cô lập cũng có mặt), sau đó gọi addEdge cho mọi cặp trong adjacency. Tiếp theo, duyệt tất cả các đỉnh: mỗi đỉnh chưa được thăm sẽ bắt đầu một thành phần mới (tăng bộ đếm), rồi chạy DFS/BFS từ đỉnh đó để đánh dấu toàn bộ thành phần là đã thăm.
Bạn phải dùng lớp Graph (được cung cấp trong graph), không dùng các cấu trúc dựng sẵn của ngôn ngữ (map, set) để biểu diễn quan hệ kề. Dữ liệu phụ trợ cho thuật toán (tập hợp các đỉnh đã thăm, ngăn xếp) có thể dùng các kiểu trong thư viện chuẩn.
Tự làm thử
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", countConnectedComponents(adjacency, m, vertices, n));
return 0;
}
Tất cả bài học trong Đồ thị, chuỗi cấu trúc dữ liệu #9
Tự luyện tập: Trình biên dịch C online