Đồ thị - Biểu diễn đồ thị (B1)
Điểm: 100
Cho đồ thị vô hướng ~G = <V, E>~ được biểu diễn dưới dạng danh sách cạnh.
Yêu cầu: Hãy viết chương trình thực hiện chuyển đổi biểu diễn đồ thị sang ma trận kề.
Input: File văn bản DSC_MTK.INP gồm:
- Dòng đầu tiên chứa hai số nguyên ~n~ và ~m (1≤n≤1000;1≤m≤n(n-1)/2)~
- ~m~ dòng tiếp theo, mỗi dòng là hai số nguyên ~u, v~ biểu diễn cạnh ~(u,v)~ của đồ thị ~(1≤u,v≤n)~. Các cạnh được liệt kê theo thứ tự tăng dần của điểm đầu.
Output: File văn bản DSC_MTK.OUT:
- In ra ma trận kề tương ứng của đồ thị.
Ví dụ:
Sample Input:
5 9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5
Sample Output:
0 1 1 1 0
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
0 1 1 1 0
Điểm: 100
Cho đồ thị vô hướng ~G = <V, E>~ được biểu diễn dưới dạng danh sách cạnh.
Yêu cầu: Hãy viết chương trình thực hiện chuyển đổi biểu diễn đồ thị sang danh sách kề.
Input: File DSC_DSK.INP gồm:
- Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1≤n≤1000;1≤m≤n(n-1)/2)~
- ~m~ dòng tiếp theo, mỗi dòng là hai số nguyên ~u, v~ biểu diễn cạnh ~(u,v)~ của đồ thị ~(1≤u,v≤n)~. Các cạnh được liệt kê theo thứ tự tăng dần của điểm đầu.
Output: File DSC_DSK.OUT:
- In ra danh sách kề tương ứng của đồ thị. (Liệt kê theo thứ tự tăng dần của các đỉnh)
Ví dụ:
Sample Input:
5 9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5
Sample Output:
1 : 2 3 4
2 : 1 3 4 5
3 : 1 2 4 5
4 : 1 2 3 5
5 : 2 3 4
Điểm: 100
Cho đồ thị vô hướng ~G = <V, E>~ được biểu diễn dưới dạng ma trận kề.
Yêu cầu: Hãy viết chương trình thực hiện chuyển đổi biểu diễn đồ thị dưới dạng danh sách cạnh.
Input: File MTK_DSC.INP gồm:
- Dòng đầu tiên chứa số n là số đỉnh của đồ thị (1≤n≤1000)
- n dòng tiếp theo, mỗi dòng ghi n số biểu diễn ma trận kề của đồ thị.
Output: File MTK_DSC.OUT:
- In ra danh sách cạnh tương ứng theo thứ tự đỉnh đầu tăng dần.
Ví dụ:
Sample Input:
5
0 1 1 1 0
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
0 1 1 1 0
Sample Output:
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5
Điểm: 100
Cho đồ thị vô hướng ~G = <V, E>~ được biểu diễn dưới dạng ma trận kề.
Yêu cầu: Hãy viết chương trình thực hiện chuyển đổi biểu diễn đồ thị dưới dạng danh sách kề.
Input: File văn bản MTK_DSK.INP gồm:
- Dòng đầu tiên chứa số ~n~ là số đỉnh của đồ thị ~(1≤n≤1000)~
- ~n~ dòng tiếp theo, mỗi dòng ghi ~n~ số biểu diễn ma trận kề của đồ thị.
Output: File văn bản MTK_DSK.OUT:
- In ra danh sách kề tương ứng của đồ thị (Liệt kê theo thứ tự đỉnh tăng dần)
Ví dụ:
Sample Input:
5
0 1 1 1 0
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
0 1 1 1 0
Sample Output:
1 : 2 3 4
2 : 1 3 4 5
3 : 1 2 4 5
4 : 1 2 3 5
5 : 2 3 4
Điểm: 100
Cho đồ thị vô hướng ~G = <V, E>~ được biểu diễn dưới dạng ma danh sách kề.
Yêu cầu: Hãy viết chương trình thực hiện chuyển đổi biểu diễn đồ thị dưới dạng ma trận kề.
Input: File văn bản DSK_MTK.INP gồm:
- Dòng đầu tiên chứa số ~n~ là số đỉnh của đồ thị ~(1≤n≤1000)~
- ~n~ dòng tiếp theo, dòng thứ ~i~ ghi danh sách kề của đỉnh thứ ~i (1≤i≤n)~
Output: File văn bản DSK_MTK.OUT gồm:
- In ra ma trận kề tương ứng của đồ thị.
Ví dụ:
Sample Input:
5
2 3 4
1 3 4 5
1 2 4 5
1 2 3 5
2 3 4
Sample Output:
0 1 1 1 0
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
0 1 1 1 0
Điểm: 100
Cho đồ thị vô hướng ~G = <V, E>~ được biểu diễn dưới dạng ma danh sách kề.
Yêu cầu: Hãy viết chương trình thực hiện chuyển đổi biểu diễn đồ thị dưới dạng ma trận kề.
Input: File văn bản DSK_DSC.INP gồm:
- Dòng đầu tiên chứa số ~n~ là số đỉnh của đồ thị ~(1≤n≤1000)~
- ~n~ dòng tiếp theo, dòng thứ ~i~ ghi danh sách kề của đỉnh thứ ~i (1≤i≤n)~
Output: File văn bản DSK_DSC.OUT gồm:
- In ra danh sách cạnh tương ứng của đồ thị. Các cạnh được liệt kê theo thứ tự tăng dần của điểm đầu, trùng điểm đầu thì xét đỉnh cuối tăng dần.
Ví dụ:
Sample Input:
5
2 3 4
1 3 4 5
1 2 4 5
1 2 3 5
2 3 4
Sample Output:
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5