Cho mình xin lời giải bài 3 với :)
Có liên quan gì tới việc hợp nhất cây trong thuật toán tìm cây khung nhỏ nhất không vậy?
Bài 3 chỉ việc định chiều các cạnh xen kẽ nhau. Cụ thể là:
Gọi p(i) là nút cha của i.
Gọi f(i) = 0 nếu có cạnh p(i)->i, f(i) = 1 nếu có cạnh i->p(i).
Sau đó thì chỉ việc DFS từ đỉnh 1, trong lúc duyệt từ đỉnh u sang đỉnh v thì gán f(v) = 1 - f(u).
Làm như vậy thì đường đi dài nhất sẽ là 1.
Cho em hỏi là bài 5 làm kiểu gì vậy ạ ?