邻接表

一句话理解

邻接表给每个点一个邻居列表。

为什么要学

稀疏图首选。

讲解

vector g[N]; 或 vector 存权。空间 O(n+m)。

例子

vector<int> g[N];
g[u].push_back(v);

只存存在的边。

常见错误

• 无向只 push 一次。
• 每次把图当矩阵扫 n。