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

    solution

    Đề bài: [Toán rời rạc] Bậc của đỉnh và định lý bắt tay

    Trong đồ thị vô hướng, bậc của một đỉnh là số cạnh kề với nó. Định lý bắt tay phát biểu rằng tổng bậc của mọi đỉnh bằng hai lần số cạnh:

    ∑vdeg⁡(v)=2m.\sum_{v} \deg(v) = 2m.∑v​deg(v)=2m.

    Cho đồ thị vô hướng nnn đỉnh (đánh số 1..n1..n1..n) và mmm cạnh, hãy in bậc của các đỉnh từ 111 đến nnn.

    Ví dụ: tam giác 1−2,2−3,3−11-2, 2-3, 3-11−2,2−3,3−1 thì mọi đỉnh đều có bậc 2.

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

      Dòng 1: nnn và mmm. mmm dòng tiếp theo: mỗi dòng hai đỉnh u,vu, vu,v của một cạnh.

    • 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\cdot10^50≤m≤2⋅105, không có khuyên (cạnh nối đỉnh với chính nó).

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

      Một dòng gồm nnn số: bậc của các đỉnh 1,2,…,n1, 2, \ldots, n1,2,…,n.

    Ví dụ:

    Đầu vào:

    3 3
1 2
2 3
3 1

    Đầu ra:

    2 2 2

    Giải thích:

    Tam giác: mỗi đỉnh kề 2 cạnh nên bậc đều bằng 2 → "2 2 2".

    Đang tải editor...