1#include<bits/stdc++.h>
2#include <iostream>
3using namespace std;
4
5/*
6Cho đồ thị vô hướng G=<V,E> được biểu diễn dưới dạng ma trận kề.
7Hã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ề.
8
9Input
10Dòng đầu tiên chứa số n là số đỉnh của đồ thị (1 <= n <= 1000)
11N dòng tiếp theo, mỗi dòng N số biểu diễn ma trận kề của đồ thị.
12
13Output
14In 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
15*/
16
17int n, m; //n: dinh, m: canh
18int a[1001][1001]; // ma tran ke
19vector<int> adj[1001]; // danh sach ke
20
21int main() {
22 // Chuyen NHAP, XUAT thanh file
23 freopen("lab1_4_input.INP", "r", stdin);
24 freopen("lab1_4_output.OUT", "w", stdout);
25
26 // INPUT
27 cin >> n;
28 for(int i = 1; i <= n; i++) {
29 for(int j = 1; j <= n; j++) {
30 cin >> a[i][j];
31 }
32 }
33
34 // In ra ma tran ke vua lay duoc
35// cout << "Ma tran ke: " << n << " dinh" << endl;
36// for(int i = 1; i <= n; i++) {
37// for(int j = 1; j <= n; j++) {
38// cout << a[i][j] << " ";
39// }
40// cout << endl;
41// }
42
43 // Luu vao danh sach ke
44 for(int i = 1; i <= n; i++) {
45 for(int j = 1; j <= n; j++) {
46 if(a[i][j] == 1
47 && i < j)
48 {
49 adj[i].push_back(j);
50 adj[j].push_back(i);
51 }
52 }
53 }
54
55 // OUTPUT, danh sach ke
56 for(int i = 1; i <= n; i++) {
57 cout << i << ": ";
58 for(int x: adj[i]) {
59 cout << x << " ";
60 }
61 cout << endl;
62 }
63}