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

    solution

    Đề bài: [C] Phát hiện chu trình trong mạng bạn bè bằng DSU

    Mạng xã hội có nnn người (đánh số 1..n1..n1..n) và mmm quan hệ bạn bè (đồ thị vô hướng, không cạnh tự thân). Hãy xác định mạng có chứa chu trình hay không, dùng cấu trúc DSU (Union-Find) với union-by-rank và path-compression.

    Khi thêm cạnh (u,v)(u, v)(u,v): nếu find(u)=find(v)find(u) = find(v)find(u)=find(v) → đã có chu trình.

    Ví dụ 4 đỉnh, cạnh 1−2,2−3,3−4,4−11{-}2, 2{-}3, 3{-}4, 4{-}11−2,2−3,3−4,4−1 tạo chu trình → YES.

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

      Dòng 1: nnn, mmm. mmm dòng tiếp, mỗi dòng hai số u,vu, vu,v.

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

      1≤n≤1051 \le n \le 10^51≤n≤105, 0≤m≤2⋅1050 \le m \le 2 \cdot 10^50≤m≤2⋅105, không có cạnh trùng nhau.

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

      In YES nếu có chu trình, NO nếu không.

    Ví dụ:

    Đầu vào:

    4 4
1 2
2 3
3 4
4 1

    Đầu ra:

    YES

    Giải thích:

    Bốn cạnh tạo chu trình vuông.

    Đang tải editor...