第 7 章树与图论基础#

本章目标：学会把关系建模为图，掌握 DFS、BFS、拓扑排序、并查集、最短路和最小生成树。

7.1 学习目标#

理解图的点、边、方向、权重、连通性。
掌握邻接表和邻接矩阵。
掌握 DFS、BFS 和拓扑排序。
掌握并查集、最短路、最小生成树。
能根据题意完成正确建图。

7.2 图的表示#

图 $G=(V,E)$ ，其中 $V$ 是点集， $E$ 是边集。

邻接矩阵适合稠密图：

space=O(n^2)

邻接表适合稀疏图：

space=O(n+m)

建图时要确认：

有向还是无向。
是否有边权。
是否有重边和自环。
点编号从 0 还是 1 开始。

7.3 DFS#

DFS 适合深入探索。

1
void dfs(int u) {
2
    vis[u] = true;
3
    for (int v : g[u]) {
4
        if (!vis[v]) dfs(v);
5
    }
6
}

用途：

连通块。
树的遍历。
环检测。
拓扑排序。
回溯搜索。

7.4 BFS#

BFS 按层扩展，因此能求无权图最短路。

1
queue<int> q;
2
dist[s] = 0;
3
q.push(s);
4
while (!q.empty()) {
5
    int u = q.front(); q.pop();
6
    for (int v : g[u]) {
7
        if (dist[v] == -1) {
8
            dist[v] = dist[u] + 1;
9
            q.push(v);
10
        }
11
    }
12
}

BFS 的正确性来自：第一次访问某点时，已经是最短层数。

7.5 拓扑排序#

拓扑排序用于 DAG。

Kahn 算法：

统计每个点入度。
把入度为 0 的点入队。
每弹出一个点，就删除它的出边。
如果最终点数不足 n，说明有环。

拓扑序可用于任务依赖和 DAG DP。

7.6 并查集#

并查集维护动态连通性。

1
int find(int x) {
2
    if (fa[x] == x) return x;
3
    return fa[x] = find(fa[x]);
4
}
5

6
void unite(int a, int b) {
7
    a = find(a); b = find(b);
8
    if (a != b) fa[a] = b;
9
}

路径压缩后复杂度近似 $O(1)$ ，严格为反阿克曼函数 $O(\alpha(n))$ 。

7.7 Dijkstra 最短路#

适用条件：非负边权。

核心思想：每次选择当前 dist 最小的未确定点，它的最短路已经确定。

复杂度：

O((n+m)\log n)

使用优先队列实现。

7.8 Floyd 多源最短路#

适合 n 较小的多源最短路。

状态： $d[i][j]$ 表示 i 到 j 的最短路。

转移：

d[i][j] = \min(d[i][j], d[i][k] + d[k][j])

三重循环顺序：k 在最外层。

7.9 最小生成树#

给定无向连通带权图，找一棵连接所有点且边权和最小的树。

Kruskal：

按边权排序。
从小到大尝试加边。
如果两个端点不连通，就加入并合并集合。

正确性来自割性质：跨越某个割的最小边一定可以属于某棵 MST。

7.10 易错点#

无向边忘记加两次。
BFS 入队时不标记 visited，导致重复入队。
Dijkstra 用在负权图上。
Floyd 没有初始化 $d[i][i]=0$ 。
并查集没有路径压缩导致超时。
拓扑排序建边方向反了。

7.11 练习#

统计无向图连通块数量。
用 BFS 求迷宫最短路。
判断有向图是否有环。
用并查集判断网络连通性。
实现 Dijkstra 和 Kruskal。

ACM/OI 扩展：图论竞赛模板补充#

本节补充 OIer 和 ACMer 常用的算法套路、模板、复杂度分析和易错点。写模板时默认使用 C++17，变量名尽量短，但注释要说明不变量和适用条件。

1. 并查集模板#

连通性、Kruskal、关系合并的基础结构。

1
struct DSU {
2
    vector<int> p, sz;
3
    DSU(int n = 0) { init(n); }
4
    void init(int n) {
5
        p.resize(n + 1); sz.assign(n + 1, 1);
6
        iota(p.begin(), p.end(), 0);
7
    }
8
    int find(int x) {
9
        while (x != p[x]) x = p[x] = p[p[x]];
10
        return x;
11
    }
12
    bool unite(int a, int b) {
13
        a = find(a); b = find(b);
14
        if (a == b) return false;
15
        if (sz[a] < sz[b]) swap(a, b);
16
        p[b] = a; sz[a] += sz[b];
17
        return true;
18
    }
19
};

要点：

按大小合并可减少树高。
带权并查集用于维护相对距离或奇偶关系。

2. 0-1 BFS#

边权只有 0 和 1 时，比 Dijkstra 更快。

1
deque<int> dq;
2
dist[s] = 0; dq.push_front(s);
3
while (!dq.empty()) {
4
    int u = dq.front(); dq.pop_front();
5
    if (vis[u]) continue;
6
    vis[u] = 1;
7
    for (auto [v, w] : g[u]) {
8
        if (dist[v] > dist[u] + w) {
9
            dist[v] = dist[u] + w;
10
            if (w == 0) dq.push_front(v);
11
            else dq.push_back(v);
12
        }
13
    }
14
}

要点：

只适用于权值 0/1。
复杂度 $O(n+m)$ 。

3. Dijkstra 模板#

非负边权单源最短路。

1
vector<long long> dijkstra(int s, const vector<vector<pair<int,int>>>& g) {
2
    int n = (int)g.size() - 1;
3
    vector<long long> dist(n + 1, LINF);
4
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
5
    dist[s] = 0; pq.push({0, s});
6
    while (!pq.empty()) {
7
        auto [d, u] = pq.top(); pq.pop();
8
        if (d != dist[u]) continue;
9
        for (auto [v, w] : g[u]) {
10
            if (dist[v] > d + w) {
11
                dist[v] = d + w;
12
                pq.push({dist[v], v});
13
            }
14
        }
15
    }
16
    return dist;
17
}

要点：

负权边不能用 Dijkstra。
堆中旧状态用 if (d != dist[u]) continue 跳过。

4. SPFA 判负环#

虽然 SPFA 容易被卡，但判负环仍常见。

1
queue<int> q;
2
vector<int> cnt(n + 1), inq(n + 1), dist(n + 1);
3
for (int i = 1; i <= n; ++i) q.push(i), inq[i] = 1;
4
while (!q.empty()) {
5
    int u = q.front(); q.pop(); inq[u] = 0;
6
    for (auto [v, w] : g[u]) {
7
        if (dist[v] > dist[u] + w) {
8
            dist[v] = dist[u] + w;
9
            cnt[v] = cnt[u] + 1;
10
            if (cnt[v] >= n) return true;
11
            if (!inq[v]) q.push(v), inq[v] = 1;
12
        }
13
    }
14
}

要点：

多源入队可检查全图负环。
最短路主力仍建议 Dijkstra/Bellman-Ford。

5. 树的直径#

无权树两次 BFS，带权树两次 DFS/Dijkstra。

要点：

从任意点出发找最远点 A。
从 A 出发找最远点 B。
A 到 B 距离为树直径。

训练题型：

求树直径长度。
求树上每个点到最远点距离。

本章模板背诵清单#

能在 5 分钟内写出本章第一个核心模板。
能说出每个模板的时间复杂度和空间复杂度。
能说明模板不适用的反例。
能为模板构造 3 个边界样例。
能把模板改成 0-index 或 1-index 版本。

树上与图上常用扩展#

LCA 倍增模板#

树上路径、距离、祖先判断的基础。

1
const int LOG = 20;
2
vector<int> g[N];
3
int up[N][LOG], dep[N];
4
void dfs(int u, int p) {
5
    up[u][0] = p;
6
    for (int k = 1; k < LOG; ++k) up[u][k] = up[up[u][k-1]][k-1];
7
    for (int v : g[u]) if (v != p) {
8
        dep[v] = dep[u] + 1;
9
        dfs(v, u);
10
    }
11
}
12
int lca(int a, int b) {
13
    if (dep[a] < dep[b]) swap(a, b);
14
    int diff = dep[a] - dep[b];
15
    for (int k = 0; k < LOG; ++k) if (diff >> k & 1) a = up[a][k];
16
    if (a == b) return a;
17
    for (int k = LOG - 1; k >= 0; --k) {
18
        if (up[a][k] != up[b][k]) a = up[a][k], b = up[b][k];
19
    }
20
    return up[a][0];
21
}

树上距离：dep[u]+dep[v]-2dep[lca]。
根节点父亲可设为自己。
LOG 要满足 $2^{LOG}>n$ 。

差分约束#

形如 $x_v \le x_u + w$ 的约束可建边 $u\to v$ 权 w，求最短路。

判断是否有解：检查负环。
最大化最小值常转化为最长路约束。
不等式方向必须统一。

二分图染色#

判断图是否是二分图，用 BFS/DFS 染色。

遇到已染色邻点同色则失败。
奇环存在等价于不是二分图。

欧拉路径#

一笔画问题。

无向图欧拉回路：所有点度数为偶数且连通。
无向图欧拉路径：恰有 0 或 2 个奇度点。
有向图看入度出度差。

基环树#

n 个点 n 条边的连通无向图是基环树。

先拓扑删叶找到环。
环外部分是若干树。
常见于环上 DP + 树形 DP。

高频模板训练卡#

这一组训练卡用于把“07_树与图论基础”转化为赛场识别能力。每张卡都包含题目信号、模板选择、复杂度、反例和实现检查。

卡 1：DFS 连通块#

题目信号：点边关系明显，且出现 DFS 连通块可建模信号。
优先模板：使用 DFS 连通块模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用 DFS 连通块解决一道图论题并画出建图方式。

卡 2：BFS 最短路#

题目信号：点边关系明显，且出现 BFS 最短路可建模信号。
优先模板：使用 BFS 最短路模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用 BFS 最短路解决一道图论题并画出建图方式。

卡 3：多源 BFS#

题目信号：点边关系明显，且出现多源 BFS 可建模信号。
优先模板：使用多源 BFS 模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用多源 BFS 解决一道图论题并画出建图方式。

卡 4：0-1 BFS#

题目信号：点边关系明显，且出现 0-1 BFS 可建模信号。
优先模板：使用 0-1 BFS 模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用 0-1 BFS 解决一道图论题并画出建图方式。

卡 5：拓扑排序#

题目信号：点边关系明显，且出现拓扑排序可建模信号。
优先模板：使用拓扑排序模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用拓扑排序解决一道图论题并画出建图方式。

卡 6：DAG DP#

题目信号：点边关系明显，且出现 DAG DP 可建模信号。
优先模板：使用 DAG DP 模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用 DAG DP 解决一道图论题并画出建图方式。

卡 7：并查集#

题目信号：点边关系明显，且出现并查集可建模信号。
优先模板：使用并查集模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用并查集解决一道图论题并画出建图方式。

卡 8：带权并查集#

题目信号：点边关系明显，且出现带权并查集可建模信号。
优先模板：使用带权并查集模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用带权并查集解决一道图论题并画出建图方式。

卡 9：二分图染色#

题目信号：点边关系明显，且出现二分图染色可建模信号。
优先模板：使用二分图染色模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用二分图染色解决一道图论题并画出建图方式。

卡 10：Dijkstra#

题目信号：点边关系明显，且出现 Dijkstra 可建模信号。
优先模板：使用 Dijkstra 模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用 Dijkstra 解决一道图论题并画出建图方式。

卡 11：Floyd#

题目信号：点边关系明显，且出现 Floyd 可建模信号。
优先模板：使用 Floyd 模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用 Floyd 解决一道图论题并画出建图方式。

卡 12：Bellman-Ford#

题目信号：点边关系明显，且出现 Bellman-Ford 可建模信号。
优先模板：使用 Bellman-Ford 模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用 Bellman-Ford 解决一道图论题并画出建图方式。

卡 13：SPFA 判负环#

题目信号：点边关系明显，且出现 SPFA 判负环可建模信号。
优先模板：使用 SPFA 判负环模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用 SPFA 判负环解决一道图论题并画出建图方式。

卡 14：Kruskal#

题目信号：点边关系明显，且出现 Kruskal 可建模信号。
优先模板：使用 Kruskal 模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用 Kruskal 解决一道图论题并画出建图方式。

卡 15：Prim#

题目信号：点边关系明显，且出现 Prim 可建模信号。
优先模板：使用 Prim 模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用 Prim 解决一道图论题并画出建图方式。

卡 16：树直径#

题目信号：点边关系明显，且出现树直径可建模信号。
优先模板：使用树直径模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用树直径解决一道图论题并画出建图方式。

卡 17：LCA 基础#

题目信号：点边关系明显，且出现 LCA 基础可建模信号。
优先模板：使用 LCA 基础模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用 LCA 基础解决一道图论题并画出建图方式。

卡 18：欧拉路径#

题目信号：点边关系明显，且出现欧拉路径可建模信号。
优先模板：使用欧拉路径模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用欧拉路径解决一道图论题并画出建图方式。

卡 19：差分约束#

题目信号：点边关系明显，且出现差分约束可建模信号。
优先模板：使用差分约束模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用差分约束解决一道图论题并画出建图方式。

卡 20：基环树#

题目信号：点边关系明显，且出现基环树可建模信号。
优先模板：使用基环树模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用基环树解决一道图论题并画出建图方式。

卡 21：割点桥入门#

题目信号：点边关系明显，且出现割点桥入门可建模信号。
优先模板：使用割点桥入门模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用割点桥入门解决一道图论题并画出建图方式。

卡 22：最短路计数#

题目信号：点边关系明显，且出现最短路计数可建模信号。
优先模板：使用最短路计数模板，先确认图类型。
核心不变量：访问状态、距离或集合关系在每次扩展后保持正确。
复杂度目标：DFS/BFS O(n+m)，Dijkstra O((n+m)log n)，Floyd O(n^3)。
不适用场景：边权条件不满足、图方向建反、图不连通未处理时不适用。
实现检查：检查无向边双向、编号范围、重边自环、INF 溢出。
边界样例：孤点、重边、自环、不连通、负边。
训练题型：用最短路计数解决一道图论题并画出建图方式。

本章赛前默写任务#

07_树与图论基础：详细训练清单#

本清单用于把章节知识拆成可执行的小任务，偏 OI/ACM 赛场使用。

训练点 1：DFS#

识别信号：题面出现与“DFS”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“DFS”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 2：BFS#

识别信号：题面出现与“BFS”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“BFS”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 3：多源 BFS#

识别信号：题面出现与“多源 BFS”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“多源 BFS”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 4：0-1 BFS#

识别信号：题面出现与“0-1 BFS”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“0-1 BFS”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 5：拓扑排序#

识别信号：题面出现与“拓扑排序”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“拓扑排序”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 6：DAG DP#

识别信号：题面出现与“DAG DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“DAG DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 7：并查集#

识别信号：题面出现与“并查集”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“并查集”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 8：带权并查集#

识别信号：题面出现与“带权并查集”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“带权并查集”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 9：二分图染色#

识别信号：题面出现与“二分图染色”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“二分图染色”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 10：Dijkstra#

识别信号：题面出现与“Dijkstra”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Dijkstra”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 11：Floyd#

识别信号：题面出现与“Floyd”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Floyd”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 12：Bellman-Ford#

识别信号：题面出现与“Bellman-Ford”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Bellman-Ford”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 13：SPFA 负环#

识别信号：题面出现与“SPFA 负环”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“SPFA 负环”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 14：Kruskal#

识别信号：题面出现与“Kruskal”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Kruskal”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 15：Prim#

识别信号：题面出现与“Prim”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Prim”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 16：树直径#

识别信号：题面出现与“树直径”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“树直径”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 17：LCA#

识别信号：题面出现与“LCA”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“LCA”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 18：差分约束#

识别信号：题面出现与“差分约束”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“差分约束”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 19：DFS#

识别信号：题面出现与“DFS”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“DFS”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

ぬくぬくうちにゃ💤

第 7 章 树与图论基础#