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ị có phải là cây

    Cho đồ thị vô hướng nnn đỉnh và mmm cạnh. Hãy kiểm tra xem đồ thị có phải là một cây hay không. Một đồ thị là cây khi và chỉ khi nó liên thông và có đúng n−1n-1n−1 cạnh (tương đương: liên thông và không có chu trình).

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

      Dòng đầu chứa nnn và mmm. mmm dòng tiếp theo, mỗi dòng hai số u vu\ vu v mô tả 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\cdot 10^50≤m≤2⋅105. Đồ thị có thể có cạnh lặp hoặc khuyên.

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

      In YES nếu đồ thị là cây, ngược lại in NO.

    Ví dụ:

    Đầu vào:

    4 3
1 2
2 3
3 4

    Đầu ra:

    YES

    Giải thích:

    Do thi lien thong, 4 dinh va 3 canh, khong chu trinh -> la cay -> YES.

    Đang tải editor...