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

    solution

    Đề bài: [C] Phân rã hoán vị chỗ ngồi thành các chu trình

    Trong một buổi đổi chỗ ngồi, sinh viên iii chuyển đến vị trí aia_iai​. Mảng aaa là một hoán vị của 0,1,…,n−10, 1, \dots, n-10,1,…,n−1. Hãy phân rã hoán vị thành các chu trình: bắt đầu từ chỉ số chưa thăm nhỏ nhất, đi theo i→ai→aai→…i \to a_i \to a_{a_i} \to \dotsi→ai​→aai​​→… cho đến khi quay lại.

    Ví dụ: a=[1,2,0,4,3]a = [1, 2, 0, 4, 3]a=[1,2,0,4,3] ⇒ chu trình 1: 0 1 2 (vì 0→1→2→00\to 1\to 2\to 00→1→2→0); chu trình 2: 3 4 (vì 3→4→33\to 4\to 33→4→3). Tổng số chu trình =2= 2=2.

    • Định dạng đầu vào:
      • Dòng 1: số nguyên nnn.
      • Dòng 2: nnn số nguyên là một hoán vị của 0..n−10..n-10..n−1.
    • Ràng buộc đầu vào:

      1≤n≤10001 \le n \le 10001≤n≤1000; aaa là hoán vị của 0..n−10..n-10..n−1.

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

      Mỗi chu trình in trên một dòng (các chỉ số theo thứ tự đi, cách nhau dấu cách). Cuối cùng in tổng số chu trình trên một dòng riêng.

    Ví dụ:

    Đầu vào:

    5
1 2 0 4 3

    Đầu ra:

    0 1 2
3 4
2

    Giải thích:

    Chu trình {0,1,2} và {3,4}, tổng 2 chu trình.

    Đang tải editor...