Triển khai (phần 1)
Bài học 5 trên 9 trong khóa học Thuật toán Kruskal: thuật toán trên đồ thị của Coddy.
Chúng ta bắt đầu với cấu trúc hợp nhất và tìm kiếm, bộ máy phát hiện chu trình.
Thử thách
Trung bìnhPhép kiểm tra chu trình của Kruskal dựa vào union-find. Trước tiên, hãy xây dựng cấu trúc đó để đếm các thành phần liên thông.
Viết một hàm tên là countSets, nhận n và mảng edges phẳng (các bộ ba [u, v, w, ...], đồ thị vô hướng; ở đây bỏ qua trọng số), rồi trả về số thành phần liên thông, được tính bằng union-find.
Ví dụ, với 4 đỉnh và các cạnh [0,1,5, 2,3,5], có 2 thành phần: {0,1} và {2,3}.
Tự làm thử
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// Viết code ở đây
return 0;
}
Tự kiểm traBài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.
Tất cả bài học trong Thuật toán Kruskal: thuật toán trên đồ thị
2Thuật toán
Cách hoạt động?Mã giảTriển khai (phần 1)Triển khai (phần 2)
Độ phức tạp thời gian và không gianTự luyện tập: Trình biên dịch C online