Chuyển Đổi Danh Sách Cạnh Sang Danh Sách Kề Đồ Thị
Biểu diễn đồ thị là bước khởi đầu bắt buộc của mọi bài toán đồ thị (BFS, DFS, Dijkstra). Danh sách cạnh (Edge List) thường được cung cấp ở đầu vào, nhưng danh sách kề (Adjacency Li…
Tiến độ của tôi ở bài này
Điểm đượ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: python-basics, dictionary-and-lists.
Nội dung đề bài
Mô tả bài toán
Biểu diễn đồ thị là bước khởi đầu bắt buộc của mọi bài toán đồ thị (BFS, DFS, Dijkstra). Danh sách cạnh (Edge List) thường được cung cấp ở đầu vào, nhưng danh sách kề (Adjacency List) là cấu trúc tối ưu cho phép duyệt các đỉnh láng giềng trong O(deg(u)).
Yêu cầu
Cho một đồ thị vô hướng gồm N đỉnh (được đánh số từ 1 đến N) và M cạnh. Chuyển danh sách cạnh thành danh sách kề của từng đỉnh.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không truyền lời nhắc vào
input(). Lời nhắc sẽ bị in vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
Đọc từ stdin:
- Dòng đầu chứa 2 số nguyên N, M (1 ≤ N ≤ 104, 0 ≤ M ≤ 105).
- M dòng tiếp theo, mỗi dòng chứa 2 số nguyên u, v mô tả một cạnh vô hướng nối đỉnh u và đỉnh v.
Output
In ra danh sách kề của từng đỉnh từ 1 đến N. Với mỗi đỉnh i:
- In định dạng:
i: v1 v2 ... vk(trong đó các đỉnh kề được sắp xếp tăng dần). - Nếu đỉnh i không có đỉnh kề nào (đỉnh cô lập), in
i:(sau dấu hai chấm không có số nào).
Ví dụ
Input
4 3
1 2
1 3
2 4Output
1: 2 3
2: 1 4
3: 1
4: 2Gợ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.