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] Tô màu tham lam đếm số màu

    Cho đồ thị vô hướng đơn nnn đỉnh (đánh số 0..n−10..n-10..n−1). Thực hiện tô màu tham lam (greedy): duyệt các đỉnh theo thứ tự 0,1,…,n−10,1,\dots,n-10,1,…,n−1; với mỗi đỉnh, gán cho nó màu nhỏ nhất (số nguyên không âm) chưa bị các đỉnh kề đã tô sử dụng. Hãy in tổng số màu đã dùng.

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

      Dòng đầu chứa nnn và mmm (số cạnh). mmm dòng sau, mỗi dòng hai số u vu\ vu v là một cạnh.

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

      1≤n≤10001 \le n \le 10001≤n≤1000, 0≤m≤n(n−1)/20 \le m \le n(n-1)/20≤m≤n(n−1)/2, không có cạnh lặp/khuyên.

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

      Một dòng: số màu mà thuật toán tham lam đã dùng.

    Ví dụ:

    Đầu vào:

    3 3
0 1
1 2
0 2

    Đầu ra:

    3

    Giải thích:

    Tam giác $K_3$: đỉnh 0 màu 0, đỉnh 1 màu 1, đỉnh 2 màu 2 — dùng 3 màu.

    Đang tải editor...