CTDL> bài 18.A22 CTDL> bài [Graph].Kiểm tra chu trình trên đồ thị có hướng.
[Graph].Kiểm tra chu trình trên đồ thị có hướng.
Cho đồ thị có hướng G = (V, E) được biểu diễn dưới dạng danh sách cạnh. Hãy xác định xem đồ thị có tồn tại chu trình hay không? Bài này các bạn cài đặt bằng 3 phương pháp : DFS, BFS và DSU.
Input Format
Dòng đầu tiên là 2 số n, m, tương ứng với số lượng đỉnh, cạnh của đồ thị. Các đỉnh của đồ thị được đánh số từ 1 tới n. m dòng tiếp theo mỗi dòng chứa đỉnh u, v (u != v) tương ứng với một cạnh của đồ thị.(1=<=n<=1000; 1<=m<=n*(n-1)/2)
Constraints
.
Output Format
In ra 1 nếu đồ thị tồn tại chu trình, ngược lại in ra 0.
Ví dụ:
Dữ liệu vào
10 16
9 10
6 4
6 1
6 3
9 2
3 9
9 4
3 8
3 5
6 7
6 10
9 6
6 8
3 7
6 5
9 7
Dữ liệu ra
1
Comments