B3643 图的存储
对应章节：五、数据结构与算法 → （十五） 图论入门。
（一） 任务与输出目标
把无向图输出成邻接矩阵与按编号排序的邻接表。
（二） 建模与推导
读到边 u-v 时，矩阵两个对称位置都置 1，邻接表则在 u 后追加 v、在 v 后追加 u。矩阵表示任意两点是否直接相连，列表只保存实际邻居。每行邻接表先输出列表长度，即度数，再输出排序后的邻居。两个表示的内容要相互对应。
（三） 手算与过程
边 1-2、2-3：第 2 行矩阵为 1,0,1，邻接表第 2 行为“2 1 3”，先输出度数 2。
（四） 带注释实现
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> matrix(n + 1, vector<int>(n + 1, 0)), g(n + 1);
while (m--) {
int u, v;
cin >> u >> v;
matrix[u][v] = matrix[v][u] = 1;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
cout << matrix[i][j] << ' ';
cout << '\n';
}
for (int i = 1; i <= n; ++i) {
sort(g[i].begin(), g[i].end()); // 原输入顺序不一定等于邻居编号顺序。
cout << g[i].size();
for (int v : g[i])
cout << ' ' << v;
cout << '\n';
}
}
signed main() {
ios::sync_with_stdio(false); // 关闭同步，使用 cin 与 cout 完成输入输出。
cin.tie(0), cout.tie(0);
int T = 1; // 本题读入一组数据。
// cin >> T; // 题目给出测试组数时开启，并在 solve 中处理一组。
while (T--)
solve();
}（五） 复杂度
矩阵输出 \(O(n^2)\)，列表排序上界 \(O(m\log m)\)；空间 \(O(n^2+m)\)。