Nội dung Bài tập
- Mã:
- AdjList
- Tên:
- Biểu diễn đồ thị bằng danh sách kề
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- phucnq
Cho một đơn đồ thị vô hướng G = (V, E). Trong đó: V là tập các đỉnh khác rỗng, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.
Quảng cáo
Ví dụ đồ thị sau:
0
/ \
1 2
/
3
Ta có: V := {0; 1; 2; 3} và E := {0; 1}, {0, 2}, {1, 3}.
Hãy viết chương trình biểu diễn đồ thị dưới dạng ma trận kề và danh sách kề.
Input:
- Dòng đầu tiên: số nguyên dương n - số đỉnh của đồ thị
- Các dòng tiếp theo, mỗi dòng gồm 2 số nguyên a, b biểu diễn cạnh nối đỉnh a và đỉnh b của đồ thị. (0 <= a, b < n)
Output:
- n dòng đầu tiên, mỗi dòng biểu diễn danh sách các đỉnh kề với đỉnh i (0 <= i < n). Xuất theo ví dụ mẫu. Thứ tự các đỉnh xếp theo chiều tăng dần.
- Ma trận vuông n * n biểu diễn ma trận kề của đồ thị trên.
Ví dụ:
Input
Output
4
0 1
0 2
1 3
{0} := [1, 2]
{1} := [0, 3]
{2} := [0]
{3} := [1]
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...