Phát hiện chu trình trong đồ thị vô hướng
Một mạng lưới đường đi nhỏ có thể chứa vòng. Nếu xuất phát từ một điểm, đi theo các đoạn
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Một mạng lưới đường đi nhỏ có thể chứa vòng. Nếu xuất phát từ một điểm, đi theo các đoạn đường rồi quay lại đúng điểm xuất phát mà không dùng lại đoạn nào, mạng lưới đó có chu trình. Bài này chỉ hỏi "có hay không", không cần chỉ ra chu trình cụ thể.
Yêu cầu
Cho đồ thị vô hướng đơn gồm n đỉnh đánh số 1..n và m cạnh: không có khuyên (cạnh nối một đỉnh với chính nó) và giữa hai đỉnh bất kỳ có nhiều nhất một cạnh. Hãy in ra YES nếu đồ thị có ít nhất một chu trình, ngược lại in NO. Chu trình ở đây phải gồm ít nhất 3 đỉnh phân biệt.
Quy ước nộp bài
Nộp tệp solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Chỉ in đúng YES hoặc NO bằng chữ in hoa, không in thêm gì khác. Chỉ dùng thư viện chuẩn C++17.
Input
- Dòng đầu tiên: hai số nguyên n, m (1 <= n <= 8, 0 <= m <= 12).
- m dòng tiếp theo: mỗi dòng hai số nguyên u, v (1 <= u, v <= n, u != v) mô tả
một cạnh vô hướng giữa u và v.
- Nếu m = 0 thì không có dòng cạnh nào.
Output
In ra stdout duy nhất một từ: YES nếu tồn tại chu trình, NO nếu đồ thị là một rừng (hợp của các cây).
Ràng buộc
- Đồ thị đơn: không có cạnh bội và không có khuyên.
- Chu trình dài nhất có thể chỉ gồm 3 đỉnh với dữ liệu nhỏ này.
- Mỗi bộ dữ liệu có thời gian chạy 1 giây.
Ví dụ 1
Input
4 3
1 2
2 3
3 4
Output
NO
Ví dụ 2
Input
3 3
1 2
2 3
3 1
Output
YES
Giải thích
Dữ liệu vào:
Ba cạnh 1-2, 2-3, 3-1 khép kín thành tam giác, nên kết quả là:
Còn với dữ liệu vào
ta chỉ có một đường thẳng, không có vòng nào, nên kết quả là NO.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
