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 tập đỉnh tạo đồ thị đầy đủ

    Cho đồ thị vô hướng đơn GGG với nnn đỉnh (đánh số 1..n1..n1..n) và mmm cạnh. Cho một tập gồm qqq đỉnh. Hãy kiểm tra xem tập đỉnh đó có tạo thành một đồ thị con đầy đủ (clique) hay không — tức là mọi cặp đỉnh trong tập đều có cạnh nối trực tiếp.

    • Đị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 là một cạnh. Dòng kế chứa qqq. Dòng cuối chứa qqq đỉnh phân biệt của tập cần kiểm tra.

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

      1≤n≤20001 \le n \le 20001≤n≤2000, 0≤m≤min⁡(n(n−1)/2,105)0 \le m \le \min(n(n-1)/2, 10^5)0≤m≤min(n(n−1)/2,105), 1≤q≤n1 \le q \le n1≤q≤n.

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

      In YES nếu tập đỉnh tạo đồ thị con đầy đủ, ngược lại in NO.

    Ví dụ:

    Đầu vào:

    4 5
1 2
1 3
2 3
3 4
2 4
3
2 3 4

    Đầu ra:

    YES

    Giải thích:

    Cac cap (2,3),(2,4),(3,4) deu co canh nen tap {2,3,4} la clique -> YES.

    Đang tải editor...