Đề bài này hơi khó hiểu chút, cho một mạng gồm n router, tính khoảng thời gian time out để gửi lại gói tin khi xảy ra lỗi. Khoảng thời gian này là khoảng thời gian tối thiểu khi chọn 1 router trong mạng làm router trung tâm mà gói tin vẫn có thể đến tất cả các router còn lại.
Giải thích : Test 2: Chọn 2 làm router trung tâm thì khoảng thời gian cần thiết sẽ là 1.
Test 3 : Chọn 1 làm router trung tâm khoảng thời gian cần thiết là 2.
Giải thuật : Hãy liên tưởng đến bài toán tìm đường dài nhất trong đồ thị thì bài toán này sẽ là tìm số lượng điểm nhiều nhất giữa 2 router bất kì. Vẫn DFS 2 lần, lần 1 tại điểm bất kì và lần 2 tại điểm dài nhất đã tìm được ở lần 1.
Thời gian cần thiết sẽ là tổng số node lớn nhất giữa 2 node + 1 chia 2.
Test 3 : Chọn 1 làm router trung tâm khoảng thời gian cần thiết là 2.
Giải thuật : Hãy liên tưởng đến bài toán tìm đường dài nhất trong đồ thị thì bài toán này sẽ là tìm số lượng điểm nhiều nhất giữa 2 router bất kì. Vẫn DFS 2 lần, lần 1 tại điểm bất kì và lần 2 tại điểm dài nhất đã tìm được ở lần 1.
Thời gian cần thiết sẽ là tổng số node lớn nhất giữa 2 node + 1 chia 2.
Solution