Appearance
图搜索、回溯与并查集
本章处理“状态之间存在连接关系”的问题：DFS/BFS 遍历显式或隐式图，回溯枚举决策树，并查集维护动态连通分量。三者都涉及搜索空间，但解决目标和状态维护方式不同。
图、网格与 Flood Fill
网格题可把每个格点视为图节点。开始前先确定方向数（四方向或八方向）、访问条件、访问标记，以及是否允许修改原网格。
cpp
constexpr int dr[] = {-1, 1, 0, 0};
constexpr int dc[] = {0, 0, -1, 1};
void dfs(int row, int col) {
visited[row][col] = true; // 进入时立即标记，防止环中重复访问
for (int direction = 0; direction < 4; ++direction) {
const int nr = row + dr[direction];
const int nc = col + dc[direction];
if (inside(nr, nc) && !visited[nr][nc] && allowed(nr, nc)) {
dfs(nr, nc);
}
}
}- 岛屿数量 / 面积：扫描到未访问陆地就计数一次并 flood fill；
- 被围绕区域：从边界合法节点反向标记，最后处理未标记区域；
- 多源 BFS：把所有起点同时入队，例如腐烂橘子、最近距离；
- 最短无权路径：使用 BFS，并在入队时标记，避免重复入队；
- 带非负权最短路：使用 Dijkstra，而不是普通 BFS。
递归 DFS 在深图或大网格上可能栈溢出，需要时改用显式 std::stack；图中存在环时必须维护访问状态。
回溯：枚举决策树
回溯用于组合、排列、子集、切分和棋盘搜索。每层明确当前路径、候选集合、终止条件与剪枝规则：
cpp
void backtrack(int start) {
if (is_complete()) {
answers.push_back(path);
return;
}
for (int i = start; i < static_cast<int>(choices.size()); ++i) {
if (!valid(choices[i])) continue;
path.push_back(choices[i]);
backtrack(next_start(i));
path.pop_back(); // 撤销选择
}
}- 排列：用
used[i]保证一个元素只选一次，下一层通常仍从 0 开始； - 组合 / 子集：传
start，下一层从i + 1开始，避免顺序不同造成重复； - 允许重复选取：下一层可以仍从
i开始； - 含重复元素去重：先排序，同一递归层使用
i > start && nums[i] == nums[i - 1]跳过； - 棋盘题：选择后要恢复现场；可用列和对角线集合把合法性检查降为 O(1)。
回溯最坏通常是指数级。排序、剩余元素不足、目标上下界和可行性预判等剪枝决定实际效率；剪枝前要证明不会丢失合法解。
并查集（Union-Find）
并查集适合动态维护“哪些节点属于同一连通块”，常用于连通块数量、冗余边检测、账户合并和 Kruskal 最小生成树。
cpp
class DSU {
public:
explicit DSU(int n) : parent_(n), size_(n, 1) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int find(int x) {
return parent_[x] == x ? x : parent_[x] = find(parent_[x]);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (size_[a] < size_[b]) std::swap(a, b);
parent_[b] = a;
size_[a] += size_[b];
return true;
}
private:
std::vector<int> parent_;
std::vector<int> size_;
};路径压缩加按大小 / 按秩合并后，单次操作均摊为 O(α(n))，其中反阿克曼函数增长极慢。并查集擅长连通性，不直接给出具体路径，也不能高效处理任意删边；这类需求通常需要其他动态图结构或离线逆序技巧。
如何选择
| 目标 | 常见选择 |
|---|---|
| 遍历所有可达状态 | DFS / BFS |
| 无权图最短路径 | BFS |
| 枚举所有满足约束的方案 | 回溯 + 剪枝 |
| 反复合并集合并查询连通性 | 并查集 |
| 非负权图最短路径 | Dijkstra |