📇
邻接表：每个节点的「联系人名单」
上一课我们用 n×n 大表（邻接矩阵）存图——图一稀疏，表里 99% 是 0。换个思路：给每个节点一张自己的「联系人名单」，只记「和谁直接相连」：adj[i] 是一个列表，存所有「i→j 有边」的 j——这就是邻接表，稀疏图的省地方案。
💡 打个比方
别再造大表格了——每个站点自带一张「联系人名单」。想象一个 1000 站、只有 100 条线的地铁网：1000×1000 的大表里只有 200 个格子是 1（每条无向边占 2 格），其余 999800 格全是 0——99.98% 的纸面在记「没这回事」。换个存法：每个站点口袋里揣个小本子，本子上只写「我直接连着哪些站」。站 A 的本子写「B、D」；B 线多，本子就厚一点。所有本子合起来 = 邻接表：C++ 里写成 vector所有直达邻居。加无向边 u—v：u 的本子写 v、v 的本子写 u（两条都记）；加有向边 u→v：只在 u 的本子写 v。列表长度 = 该节点的度（有向图是出度）——空间从 O(n²) 降到 O(n+m)，只存真正存在的边。
术语：邻接表（adj[i] = 「i→j 有边」的所有 j 的列表）、vector（长度可变的列表，push_back 追加、size() 数长度）、出度（有向图：出去的边）、自环（节点指向自己的边）、重边（两节点间多条平行边）、稀疏图（边少，m ≪ n²）/稠密图（边多）。
🖼️ 大图看明白
🧩 子任务 1：稀疏图的浪费账——1000 节点 100 条边，矩阵 99% 是 0
🎯 小目标：会算「矩阵到底浪费了多少」，理解稀疏图只该存边、不该存 0——这就是邻接表的动机。
// 算账（无向图，int 矩阵，1 个 int = 4 字节）：
// n = 1000 个节点，m = 100 条边
// 矩阵：1000×1000 = 100 万格 × 4B = 4 MB
// 1 的个数：100 条边 × 2 格（无向对称）= 200 个 1
// 0 的个数：1000000 - 200 = 999800 → 99.98% 是 0！
//
// 真正有用的信息只有「哪 200 格是 1」（哪 100 对节点相连）
// 只存边：200 个数字 × 4B = 800 B ≈ 0.8 KB（外加 1000 个空名单的开销）
// 4 MB vs 1 KB —— 大表把 99% 的地面用来记「没这回事」
✅ 小检查：① n=1000、m=100（无向），矩阵里 1 的总数是多少？0 占百分之几？② 若改成有向图（100 条有向边），1 的总数变成多少？③ 什么时候 n² 比 2m 大得多？这说明该用什么存？
看看答案
① 200 个 1（每条无向边占对称 2 格）；0 占 999800/1000000 = 99.98%。
② 100 个 1——有向边只占 1 格（不写对称格），浪费更夸张。
③ 当 m ≪ n²/2（稀疏图，边远少于「格子的一半」）时——矩阵 99% 以上是 0，应该只存边，不存 0 → 邻接表的动机。⚠️ 易错：稠密图（m 接近 n(n-1)/2）时矩阵不浪费——格子几乎全是 1，一格格记正是它擅长的。先算密度再选存法：m/n² 很小 → 邻接表；m/n² 接近 1 → 矩阵。
🧩 子任务 2：vector<vector<int>> 邻接表——手推建图过程
🎯 小目标：会写「加边 = 往名单里 push_back」；能手推一个图建完后每个 adj[i] 的内容，并用「名单总数字 = 2m、名单长度 = 度」自查。
// 邻接表：n 个小列表（名单），adj[i] 存「i 的直达邻居」
#include <vector>
using namespace std;
const int N = 105;
vector<vector<int>> adj(N); // adj[i]：节点 i 的「联系人名单」
// 无向边 u—v：两个名单都写（对称）
void addEdge(int u, int v) {
adj[u].push_back(v); // v 记进 u 的名单
adj[v].push_back(u); // u 记进 v 的名单
}
// —— 手推：5 人朋友圈，边 1-2、1-3、2-4、4-5 ——
// 初始：adj[1..5] 全空
// 加 1-2：adj[1]={2} adj[2]={1}
// 加 1-3：adj[1]={2,3} adj[3]={1}
// 加 2-4：adj[2]={1,4} adj[4]={2}
// 加 4-5：adj[4]={2,5} adj[5]={4}
// 最终：adj[1]={2,3} adj[2]={1,4} adj[3]={1} adj[4]={2,5} adj[5]={4}
// 自查：名单数字总数 = 8 = 2 × 4 条边 ✓；名单长度 = 度（2,2,1,2,1，和 8=2×4 ✓）
✅ 小检查：① 上例 adj[4] 的内容是什么？② 五个名单里数字的总数是多少？和边数 m 什么关系？③ 再加一条边 3-5，哪两个名单会变？新总数是多少？
看看答案
① adj[4] = {2, 5}——4 的朋友是 2 和 5。
② 总数 = 8 = 2m（m=4）——每条无向边被写进 2 个名单。
③ adj[3] 变 {1,5}、adj[5] 变 {4,3}；新总数 8+2 = 10 = 2×5 ✓。⚠️ 易错：无向边要写两个名单——只写一边，以后查「2 的好友」就找不到 1，图等于变成有向的一半。有向边 u→v 才只写 adj[u] 一次。
🧩 子任务 3：账本对比——空间 O(n+m) vs O(n²)
🎯 小目标：会算邻接表的空间账 O(n+m)，并分清「什么操作矩阵快、什么操作邻接表快」——空间和时间是两笔账，谁也不全面赢。
// 账本对比（n = 1000 节点，m = 100 条无向边）：
//
// 邻接矩阵 邻接表
// 空间 n² = 100 万格(4 MB) n 个名单 + 2m = 200 个数字(~1 KB)
// → 差约 4000 倍
// 查「i-j 有边?」O(1)（看 g[i][j]） 扫 adj[i]，O(度)，最坏 O(n)
// 列 i 的邻居 扫第 i 行 O(n) 直接读名单 O(度)——通常快得多
// 取 i 的度 扫行 O(n)（或预算） adj[i].size()，O(1)
//
// 空间公式：矩阵 O(n²)；邻接表 O(n + m)（n 个空名单 + m 条边各写 1~2 处）
// 结论：稀疏图（m ≪ n²）→ 邻接表省内存；稠密图 / n 小且查边频繁 → 矩阵查边 O(1)
✅ 小检查：① n=10000、m=50000（无向）：矩阵要多少 MB？邻接表（只算数字）多少字节？差多少倍？② 「判断 i-j 是否有边」什么时候用矩阵更快？③ 「枚举 i 的所有邻居」为什么邻接表快？
看看答案
① 矩阵 10000² × 4B = 400 MB；邻接表 2m = 100000 个数字 × 4B = 400 KB（加 10000 个空名单开销，仍不到 1 MB）——差约 1000 倍。
② 稠密图、n 不大、查边次数极多时：矩阵 O(1) 一次定位；邻接表要扫名单 O(度)，最坏 O(n)。
③ 矩阵要扫 n 个格子（大多为 0 也得看）；邻接表名单里每个数字都是有效邻居，只扫 deg(i) 个就完事。⚠️ 易错：别把「省空间」当「全面更好」——查边矩阵 O(1) 还是赢。比赛经验：n ≤ 1000 且稠密 → 矩阵；n ≥ 10⁴ 或明显稀疏 → 邻接表（绝大多数题目）。
🧩 子任务 4：有向图邻接表 + 自环、重边
🎯 小目标：会建有向图邻接表（只写一边）；知道自环（u→u）push 谁、重边（多条平行边）在名单里长什么样，并记住「有向名单长度 = 出度」。
// 有向图：边 u→v 只在 u 的名单写 v：adj[u].push_back(v)（v 的名单不动）
// 名单长度 = 出度（不是度！）
//
// —— 手推：有向图 n=3，边：1→2、1→3、2→3、2→2（自环）、1→2（重边，第 2 条）——
// adj[1] = {2, 3, 2} ← 2 出现两次（两条 1→2 平行边）
// adj[2] = {3, 2} ← 含 2 自己（自环 2→2）
// adj[3] = {} ← 空名单（只有进来的边，没有出去的边）
// 出度：out1 = 3、out2 = 2、out3 = 0（和 5 = 边数 ✓，自环/重边各算一条）
//
// 规则：
// - 自环 u→u：把 u 写进 adj[u]（有向 push 1 次）
// 无向自环占 2 度（入度+1、出度+1）→ 把 u 写进 adj[u] 两次，长度才对得上
// - 重边：push 多次，名单里出现重复数字——不影响「枚举邻居」
// 「判断 u→v 有没有边」要扫名单，重复不影响结论；想快速判断 → 后面哈希表课
✅ 小检查：① 上例节点 1 的出度是多少？② adj[3] 是空名单，节点 3 还是「可达」的吗？为什么？③ 无向自环为什么 push 两次？
看看答案
① 3——名单 {2,3,2} 长度 3，重边也各算一条出边。
② 是——空名单只说明「3 没有出去的边」；1→3、2→3 是进来的边，所以从 1 或 2 出发都能走到 3。「可达」不需要自己有出边。
③ 无向自环 u—u 让 u 的度 +2（入度 +1、出度 +1），名单写两个 u，「名单长度 = 度」才继续成立。⚠️ 易错：有向图名单长度 = 出度，别当成度；自环最容易被漏掉（无向 push 两次）；重边的重复数字不是 bug——只是「数边数 / 判断有没有这条边」时要先想清楚（去重、或用集合，哈希表课见分晓）。
💻 完整代码：邻接表建有向图 + 输出每个节点的出边名单
// 题目：读入 n 个节点、m 条有向边，用邻接表建图，输出每个节点的出边名单（adj[i] 内容）。
// 输入：第 1 行 n m；接下来 m 行每行 u v（有向边 u→v）。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1); // n+1 个名单，编号 1..n
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v); // 有向边：只把 v 写进 u 的名单
}
// 输出每个节点的出边名单
for (int i = 1; i <= n; i++) {
cout << i << ":";
for (int j = 0; j < (int)adj[i].size(); j++)
cout << " " << adj[i][j];
cout << endl;
}
return 0;
}
// 样例：n=4, m=6；边：1 2 / 1 3 / 1 2 / 2 3 / 2 2 / 3 1
// 输出：1: 2 3 2 / 2: 3 2 / 3: 1 / 4:
// （1 有两条到 2 的平行边；2 有自环 2→2；4 没有出边 → 空名单）
✋ 你来试试
第 1 题：n=10000 的无向图，m=50000：矩阵要多少 MB？邻接表（只算数字）大约多少 KB？该用哪个？
矩阵 10000² × 4B = 400 MB；邻接表 2m = 100000 个数字 × 4B = 400 KB（加 10000 个空名单开销仍不到 1 MB）——差约 1000 倍，必须用邻接表。
第 2 题：n=3 的无向完全图（边 1-2、2-3、1-3）：写出三个名单的内容和每个节点的度。
adj[1] = {2,3}、adj[2] = {1,3}、adj[3] = {1,2}；每个名单 2 个数字，度都是 2，度和 6 = 2×3 条边 ✓。
第 3 题：有向图边 1→2、1→3、2→3、3→2：每个节点的出度、入度各是多少？邻接表里能直接看到入度吗？
出度：1 是 2、2 是 1、3 是 1；入度：1 是 0、2 是 2（1→2、3→2）、3 是 2（1→3、2→3）。邻接表只存出边——入度要看「反向图」或把 m 条边扫一遍数，这是它的小代价。
第 4 题（加餐）：邻接表的代价是「查边 u→v 有没有」要扫名单 O(度)。想让它像矩阵一样 O(1) 查边，可以怎么改？（预习）
把每个 adj[i] 排序后二分（O(log 度)），或把邻居放进哈希集合（期望 O(1)）——哈希表课马上就到，正好派上用场！
🎯 一句话记住：邻接表 = 每个节点的「联系人名单」：adj[i] 只记 i 的直达邻居；无向边 u—v 写两个名单、有向边 u→v 写一个；空间 O(n+m)（稀疏图省上千倍），名单长度 = 度（有向 = 出度）；代价是查边 O(度)——矩阵查边快但费内存，邻接表省内存但查边慢，先看 n 和边密再选。