Triển khai phần 1
Bài học 5 trên 9 trong khóa học Sắp xếp tô pô trong đồ thị của Coddy.
Chúng ta bắt đầu với bậc vào, trọng tâm của thuật toán Kahn.
Thử thách
DễĐộng lực của thuật toán Kahn là bậc vào của mỗi đỉnh. Trước tiên, hãy tính giá trị này.
Viết một hàm (function) tên là inDegrees, nhận n và mảng phẳng edges (các cặp có hướng u -> v), rồi trả về một mảng trong đó vị trí v là số cạnh hướng vào đỉnh v.
Ví dụ, inDegrees(4, [0,1, 0,2, 1,3, 2,3]) trả về [0, 1, 1, 2].
Tự làm thử
#include <stdlib.h>
int* inDegrees(int n, int* edges, int edges_size, int* returnSize) {
// Viết code ở đây
*returnSize = 0;
return edges;
}
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 Sắp xếp tô pô trong đồ thị
2Thuật toán
Cách hoạt động?Mã giảTriển khai phần 1Triển khai phần 2
Độ phức tạp về thời gian và bộ nhớTự luyện tập: Trình biên dịch C online