Cho một đồ thị vô hướng liên thông gồm đỉnh và cạnh. Thực hiện thuật toán DFS bắt đầu từ đỉnh 1. Hãy xác định thời điểm bắt đầu duyệt () và thời điểm kết thúc duyệt () của từng đỉnh.
Quy ước:
Bộ đếm thời gian bắt đầu từ 1.
Mỗi khi thăm một đỉnh mới hoặc duyệt xong một đỉnh, thời gian tăng lên 1 đơn vị.
Ưu tiên duyệt đỉnh có chỉ số nhỏ hơn trước.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên ().
dòng tiếp theo, mỗi dòng chứa hai số nguyên .
Kết quả:
Gồm dòng. Dòng thứ in ra hai số nguyên là và của đỉnh .
Ví dụ:
Dữ liệu:
3 2
1 2
2 3
Kết quả:
1 6
2 5
3 4
Giải thích: Vào 1 (time 1) -> Vào 2 (time 2) -> Vào 3 (time 3) -> Xong 3 (time 4) -> Xong 2 (time 5) -> Xong 1 (time 6))
