Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [C] Duyệt BFS đồ thị vô hướng — Queue bằng linked list

    Cho đồ thị vô hướng nnn đỉnh (1..n1..n1..n), mmm cạnh. Cài danh sách kề bằng mảng con trỏ động N** adj (mỗi adj[u] là một linked list các đỉnh kề). Cài Queue bằng linked list. Thực hiện BFS từ đỉnh sss. Khi duyệt một đỉnh, push các đỉnh kề chưa thăm vào queue theo thứ tự tăng dần chỉ số để đảm bảo output xác định.

    In thứ tự duyệt trên một dòng, các đỉnh cách nhau bởi đúng một khoảng trắng. Free toàn bộ adjacency list trước khi thoát.

    • Định dạng đầu vào:

      Dòng 1: nnn, mmm, sss. Tiếp theo mmm dòng: u v.

    • Ràng buộc đầu vào:

      1≤n≤1041 \le n \le 10^41≤n≤104; 0≤m≤5⋅1040 \le m \le 5 \cdot 10^40≤m≤5⋅104; 1≤s≤n1 \le s \le n1≤s≤n.

    • Định dạng đầu ra:

      Một dòng các đỉnh theo thứ tự BFS.

    Ví dụ:

    Đầu vào:

    5 4 1
1 2
1 3
2 4
3 5

    Đầu ra:

    1 2 3 4 5

    Giải thích:

    BFS từ 1: thăm 1, đẩy 2 và 3; thăm 2 đẩy 4; thăm 3 đẩy 5 → 1 2 3 4 5.

    Đang tải editor...