Thử thách cuối cùng #1
Bài học 8 trên 9 trong khóa học Sắp xếp tô pô trong đồ thị của Coddy.
Thử thách
Trung bìnhThuật toán Kahn cũng có thể dùng để phát hiện chu trình.
Viết một hàm (function) có tên hasCycle, nhận n và mảng edges phẳng (có hướng), rồi trả về 1 nếu đồ thị có chu trình hoặc 0 nếu đồ thị không có chu trình.
Gợi ý: chạy thuật toán Kahn. Nếu thuật toán sắp xếp được tất cả n đỉnh, đồ thị không có chu trình; nếu thuật toán bị kẹt khi vẫn còn đỉnh chưa được sắp xếp, đồ thị có chu trình.
Tự làm thử
#include <stdlib.h>
int hasCycle(int n, int* edges, int edges_size) {
// Viết code ở đây
return 0;
}
Tất cả bài học trong Sắp xếp tô pô trong đồ thị
Tự luyện tập: Trình biên dịch C online