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] Kiểm tra đồ thị lưỡng phân

    Một đồ thị vô hướng là lưỡng phân nếu có thể tô đỉnh bằng 2 màu sao cho mọi cạnh nối hai đỉnh khác màu (tương đương: không có chu trình lẻ). Cho đồ thị nnn đỉnh, hãy in YES nếu nó lưỡng phân, ngược lại NO.

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

      Dòng đầu: nnn, mmm. mmm dòng sau mỗi dòng một cạnh u vu\ vu v (0≤u,v<n0\le u,v<n0≤u,v<n).

    • 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.

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

      Một dòng: YES nếu lưỡng phân, ngược lại NO.

    Ví dụ:

    Đầu vào:

    4 4
0 1
1 2
2 3
3 0

    Đầu ra:

    YES

    Giải thích:

    Chu trình độ dài 4 (chẵn) nên tô được 2 màu — in `YES`.

    Đang tải editor...