存图

邻接表（推荐，稀疏图）：

vector<vector<int>> adj(n);
adj[u].push_back(v);  // 有向边 u->v
// 无向：adj[v].push_back(u);

带权边可存 pair<int,int>（邻接点, 权值）。

链式前向星：head[]、to[]、nxt[]，边多时常数更小。

并查集 Union-Find

维护连通性、Kruskal 最小生成树、离线询问：

vector<int> fa(n);
iota(fa.begin(), fa.end(), 0);
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) fa[x] = y;  // 或按 size 合并
}

路径压缩 + 按秩 / 按大小合并，均摊接近 $O(1)$。

最短路

Dijkstra（堆优化）：

priority_queue<pair<ll,int>, vector<...>, greater<...>> pq;
dist[s] = 0; pq.push({0, s});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d != dist[u]) continue;
    for (auto [v, w] : adj[u])
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
}

负环：Bellman-Ford 松弛 $n$ 轮后仍能松弛则存在负环。

拓扑排序

DAG 上按依赖顺序排列，用于课程表、DP 顺序、判环。

Kahn：入度为 0 入队，弹出时减邻点入度；若出队数 $< n$ 则有环。

DFS：vis 三色（0 未访问 / 1 访问中 / 2 完成），后序逆序即为拓扑序；遇到 1 说明有环。

最小生成树 MST

Kruskal：边按权排序，用并查集依次加边，不形成环。复杂度 $O(E \log E)$。

Prim：类似 Dijkstra，维护到当前生成树的最小边权，稠密图可用 $O(V^2)$ 朴素版。

欧拉路径 / 回路

无向图：所有点度数为偶数（欧拉回路）或恰有两个奇度点（欧拉路径，从奇度点出发）。有向图看入度出度。DFS 删边 Hierholzer 算法构造。

强连通分量 SCC

有向图缩点：Tarjan 或 Kosaraju，$O(V+E)$。用于 2-SAT、DAG 上 DP 的缩点层。

例题

例 1：最短路（堆优化 Dijkstra）
$n$ 个点 $m$ 条有向边，边权非负，求 $1$ 号点到各点最短路。邻接表 + 小根堆，弹出时若 d != dist[u] 则跳过过期状态。复杂度 $O((n+m)\log n)$。

例 2：课程表 / 拓扑排序
$n$ 门课、先修关系 $m$ 条边 $u \to v$（学完 $u$ 才能学 $v$）。Kahn 入度为 0 入队；若最终出队数 $< n$ 则存在环，无法完成所有课。否则出队顺序即一种合法选课顺序。