常用代码模板3——搜索与图论 – AcWing
DFS
尽可能往深处搜，遇到叶子节点（无路可走）回溯，恢复现场继续走
- 数据结构：stack
- 空间：需要记住路径上的点，\(O(h)\)。
- ⭐ BFS使用空间少；无最短路性质
每个DFS一定对应一个搜索树；要考虑用什么顺序遍历所有方案；DFS就是递归
剪枝：提前判断当前方案不合法，就不用继续往下走了，直接回溯
842
842. 排列数字 – AcWing题库
#include #include #include using namespace std;const int N = 10;int path[N], n;bool st[N];void dfs(int u) { if (u == n) { for (int i = 0; i < n; i++) { cout << path[i] << " "; } cout << endl; return; } for (int i = 1; i > n; dfs(0); return 0;}843
843. n-皇后问题 – AcWing题库
搜索顺序、1
每行放一个，直到n行放满，类似全排列
#include #include #include using namespace std;const int N = 20; // 对角线个数 2n-1char g[N][N];int n;bool col[N], dg[N], udg[N];void dfs(int u) { if (u == n) { for (int i = 0; i < n; i++) puts(g[i]); cout << endl; return; } for (int i = 0; i > n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { g[i][j] = '.'; } } dfs(0); return 0;}搜索顺序、2
挨个枚举每个格子，每个格子放与不放
#include #include #include using namespace std;const int N = 20; // 对角线个数 2n-1int n;char g[N][N];bool row[N], col[N], dg[N], udg[N];void dfs(int x, int y, int s) { if (y == n) x++, y = 0; if (x == n) { if (s == n) { for (int i = 0; i < n; i++) puts(g[i]); cout <> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { g[i][j] = '.'; } } dfs(0, 0, 0); return 0;}BFS
一层一层搜（稳重）
- 数据结构：queue
- 空间：需要保存一层的点，\(O(2^h)\)
- ⭐ BFS使用空间多；有最短路性质（前提图所有边权重都为 1）
844
844. 走迷宫 – AcWing题库
d 数组存储每一个点到起点距离
#include #include #include #include using namespace std;const int N = 1e2 + 10;typedef pair PII;int n, m;int map[N][N], d[N][N];PII q[N * N];int bfs() { int st = 0, ed = 0; q[0] = {0, 0}; memset(d, -1, sizeof d); d[0][0] = 0; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; while (st <= ed) { auto t = q[st++]; for (int i = 0; i = 0 && x = 0 && y > n >> m; for (int i = 0; i < n; i++) for (int j = 0; j > map[i][j]; cout << bfs(); return 0;}845 ⭐ Airbnb面试
845. 八数码 – AcWing题库
- 状态表示复杂：每个节点相当于3*3矩阵；节点如何存队列里、如何记录距离
- 可以用字符串保存，使用
unordered_map
- 可以用字符串保存，使用
- 状态转移
- 想象成3*3的位置；然后把x移动到4个位置上去判断，再恢复成字符串；难点是二维位置与一维位置间的转换
#include #include #include #include #include using namespace std;int bfs(string start) { string end = "12345678x"; queue q; unordered_map d; q.push(start); d[start] = 0; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; while (q.size()) { auto t = q.front(); q.pop(); int distance = d[t]; if (t == end) return distance; // 状态转移 int k = t.find('x'); int x = k / 3, y = k % 3; for (int i = 0; i = 0 && a = 0 && b < 3) { swap(t[k], t[a * 3 + b]); if (!d.count(t)) { d[t] = distance + 1; q.push(t); } swap(t[k], t[a * 3 + b]); } } } return -1;}int main() { cin.tie(0); string start; for (int i = 0; i > c; start += c; } cout << bfs(start) << endl; return 0;}树与图
有向图、无向图 （特殊的有向图，a->b、b->a）。只需要考虑有向图的存储方式。树是无环连通图
邻接矩阵
不太常用。开二维bool数组 G[A][B] 存储 A->B 的信息，有重边就保留一条（可以是最短边）。空间 \(O(n^2)\)，适合存储稠密图
邻接表 ⭐
常用。每个节点上开一个单链表（类似拉链法哈希表），每个链存储可到的点（次序不重要）。单链表可以数组模拟或vector（效率慢），适合存储稀疏图
DFS 树与图
\(O(n+m)\)
846 ⭐⭐
AcWing 846. 树的重心 – AcWing
#include #include #include using namespace std;const int N = 1e5 + 10; // 数据范围是10的5次方const int M = 2 * N; // 以有向图的格式存储无向图，所以每个节点至多对应2n-2条边int h[N]; // 邻接表存储树，有n个节点，所以需要n个队列头节点int e[M]; // 存储元素int ne[M]; // 存储列表的next值int idx; // 单链表指针int n; // 题目所给的输入，n个节点int ans = N; // 表示重心的所有的子树中，最大的子树的结点数目bool st[N]; // 记录节点是否被访问过，访问过则标记为true// a所对应的单链表中插入b a作为根void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }// dfs 框架/*void dfs(int u){ st[u]=true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程 for(int i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(!st[j]) { dfs(j); } }}*/// 返回以u为根的子树中节点的个数，包括u节点int dfs(int u) { int res = 0; // 存储 删掉某个节点之后，最大的连通子图节点数 st[u] = true; // 标记访问过u节点 int sum = 1; // 存储 以u为根的树 的节点数, 包括u，如图中的4号节点 // 访问u的每个子节点 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; // 因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过 if (!st[j]) { int s = dfs(j); // u节点的单棵子树节点数 如图中的size值 res = max(res, s); // 记录最大联通子图的节点数 sum += s; // 以j为根的树 的节点数 } } // n-sum 如图中的n-size值，不包括根节点4； res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数 ans = min(res, ans); // 遍历过的假设重心中，最小的最大联通子图的 节点数 return sum;}int main() { memset(h, -1, sizeof h); // 初始化h数组 -1表示尾节点 cin >> n; // 表示树的结点数 // 题目接下来会输入，n-1行数据， // 树中是不存在环的，对于有n个节点的树，必定是n-1条边 for (int i = 0; i > a >> b; add(a, b), add(b, a); // 无向图 } dfs(1); // 可以任意选定一个节点开始 u<=n cout << ans << endl; return 0;}BFS 树与图
\(O(n+m)\)
847 ⭐
AcWing 847. 图中点的层次 – AcWing
#include #include #include #include #include using namespace std;const int N = 1e5 + 10;int n, m;int h[N], e[N], ne[N], idx, d[N];void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++;}int bfs() { memset(d, -1, sizeof d); queue q; d[1] = 0; q.push(1); while (q.size()) { auto u = q.front(); q.pop(); int distance = d[u]; if (u == n) return distance; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (d[j] == -1) { d[j] = distance + 1; q.push(j); } } } return -1;}int main() { cin.tie(0); memset(h, -1, sizeof h); cin >> n >> m; for (int i = 0; i > a >> b; add(a, b); } cout << bfs(); return 0;}有向图的拓扑序列
拓扑序列：有向边uv， u在序列中都在v之前
有向无环图被称为拓扑图。有向无环图至少存在一个入度为0的点，所有入度0的点排在最前位置，然后不断删除入度为0的点
848 ⭐
848. 有向图的拓扑序列 – AcWing题库
#include #include #include #include #include using namespace std;const int N = 1e5 + 10;int n, m;int h[N], ne[N], e[N], idx, d[N];void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++;}void bfs() { queue q; queue ans; for (int i = 1; i <= n; i++) { if (!d[i]) q.push(i); } while (q.size()) { auto u = q.front(); ans.push(u); q.pop(); for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; d[j]--; if (d[j] == 0) q.push(j); } } if (ans.size() != n) cout << -1; else while (ans.size()) { cout << ans.front() <> n >> m; for (int i = 0; i > a >> b; add(a, b); d[b]++; } bfs(); return 0;}最短路
- 单源最短路：单个点到其他所有点最短距离。 （n 点数，m 边数）
- 所有边权都是正数
- 朴素Dijkstra：\(O(n^2)\) 适用于稠密图
- 堆优化版Dijkstra：\(O(mlog_2n)\) 适用于稀疏图
- 存在负权边
- 贝尔曼-福特 Bellman-Ford：\(O(nm)\)
- 优化贝尔曼-福特 SPFA：一般\(O(m)\)，最坏\(O(nm)\)
- 所有边权都是正数
- 多源汇最短路：起点与终点不确定（一对起点终点）
- 弗洛伊德 Floyd：\(O(n^3)\)
⭐ 考察侧重点是建图，定义点和边
朴素Dijkstra
利用了贪心，每次找最小的
初始化所有点到起点距离：dis[1] = 0，dis[i] = +∞
集合s：存储已经确定最短距离的点
for n次
找到不在 s 中的距离原点最近的点 t
t 加到 s 去
用 t 更新其他点的距离（从t出去所有边能否更新其他点距离）
dis[x] > dis[t] + w
849
849. Dijkstra求最短路 I – AcWing题库
稠密图，用邻接矩阵存；最短路问题里面，自环应不存在，重边应只保留距离最短的
#include #include #include #include using namespace std;const int N = 510;int n, m;int g[N][N];int dist[N];bool st[N];int dijkstra() { // 初始化 memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 路径最长n个点 for (int i = 1; i <= n; i++) { // 寻找不在s中的dist最小的点t int t = -1; for (int i = 1; i dist[i])) t = i; } // 将t加入s st[t] = true; // 更新 dist for (int i = 1; i > n >> m; memset(g, 0x3f, sizeof g); while (m--) { int a, b, c; cin >> a >> b >> c; // 解决 自环、重边 问题 if (a != b) g[a][b] = min(g[a][b], c); } int t = dijkstra(); cout << t << endl; return 0;}堆优化Dijkstra
朴素方法中，查找不在 s 中距离原点最近的点共执行 \(n^2\) 次；更新dis数组相当于遍历了所有边，共执行 m 次；**可以对这两个操作进行堆优化，前者变\(O(1)*O(n)=O(n)\)，后者变\(O(log_2n)*O(m)=O(mlog_2n)\) **
堆有两种实现方式：手写堆、优先队列（不支持修改任意一个元素操作，容易冗余）
前者有n个元素，后者可能m个元素；使用优先队列时间复杂度可能变成\(O(mlog_2m)\)
\(log_2m <= log_2n^2 = 2log_2n\) 两者是一个级别的，可以不用手写堆
851 ⭐
稀疏图，用邻接表存；
#include #include #include #include #include using namespace std;const int N = 1.5e5 + 10;int n, m;int h[N], e[N], ne[N], idx, w[N], dist[N];bool st[N];typedef pair PII;void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;}int dijkstra() { // 初始化 priority_queue<PII, vector, greater> heap; memset(dist, 0x3f, sizeof dist); heap.push({0, 1}); dist[1] = 0; while (heap.size()) { // 查找t O(logn) auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; st[ver] = true; // 更新堆 O(m) for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({w[i] + t.first, j}); } } } return dist[n] != 0x3f3f3f3f ? dist[n] : -1;}int main() { cin.tie(0); memset(h, -1, sizeof h); cin >> n >> m; for (int i = 0; i > a >> b >> c; add(a, b, c); } cout << dijkstra() << endl; return 0;}Bellman-Ford
结构体存 a,b,w 然后开个数组；执行后满足任意边 dist[b] <= dist[a] + w （三角不等式）
- for n次
- for 所有边 a,b,w
- dist[b] = min(dist[b],back[a]+w) （松弛操作）
- for 所有边 a,b,w
- back[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点
1到n的路径上有负权回路的话，最短路不存在（而spfa要求图中不能有任何负环）
迭代k次相当于从原点经过不超过k条边走到每个点的最短距离；该算法可以用于判断负环
853
853. 有边数限制的最短路 – AcWing题库
#include #include #include #include using namespace std;const int N = 510, M = 10010;int n, m, k;int dist[N], backup[N];struct Edge { int a, b, w;} edges[M];int bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < k; i++) { // IMPORTANT 避免串联 memcpy(backup, dist, sizeof dist); for (int j = 0; j n 的情况 if (dist[n] > 0x3f3f3f3f / 2) return 0x3f3f3f3f; else return dist[n];}int main() { cin.tie(0); cin >> n >> m >> k; for (int i = 0; i > a >> b >> w; edges[i] = {a, b, w}; } int t = bellman_ford(); if (t == 0x3f3f3f3f) puts("impossible"); else cout << t; return 0;}SPFA
必须图里没有负环，99%的最短路问题没有负环。用宽搜优化贝尔曼-福特算法
- 队列里存所有需要变小的节点，然后宽搜
851 ⭐
851. spfa求最短路 – AcWing题库
#include #include #include #include #include using namespace std;const int N = 1.5e5 + 10;int n, m;int h[N], e[N], ne[N], idx, w[N], dist[N];bool st[N];typedef pair PII;void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;}int spfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue q; q.push(1); st[1] = true; while (q.size()) { int t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) { q.push(j); st[j] = true; } } } } if (dist[n] == 0x3f3f3f3f) return 0x3f3f3f3f; else return dist[n];}int main() { cin.tie(0); memset(h, -1, sizeof h); cin >> n >> m; for (int i = 0; i > a >> b >> c; add(a, b, c); } int t = spfa(); if (t == 0x3f3f3f3f) puts("impossible"); else cout << t; return 0;}852 ⭐
AcWing 852. spfa判断负环 – AcWing
cnt 数组维护原点到各点的边数，如果 cnt[x] >= n 则有负环；注意一开始需要把所有点放入
#include #include #include #include #include using namespace std;const int N = 1.5e5 + 10;int n, m;int h[N], e[N], ne[N], idx, w[N], dist[N], cnt[N];bool st[N];typedef pair PII;void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;}bool spfa() { // memset(dist, 0x3f, sizeof dist); // dist[1] = 0; queue q; for (int i = 1; i dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) return true; if (!st[j]) { q.push(j); st[j] = true; } } } } return false;}int main() { cin.tie(0); memset(h, -1, sizeof h); cin >> n >> m; for (int i = 0; i > a >> b >> c; add(a, b, c); } if (spfa()) puts("Yes"); else puts("No"); return 0;}Floyed
- 邻接矩阵 d
- for k=1 k<=n k++
- for i=1 i<=n i++
- for j=1 j<=n j++
- d(i,j) = min(d(i,j),d(i,k)+d(k,j))
- for j=1 j<=n j++
- for i=1 i<=n i++
基于DP，k,i,j 从 i 点出发只经过 1~k 中间点到达 j 的最短距离
854
854. Floyd求最短路 – AcWing题库
#include #include #include #include using namespace std;const int N = 210;int n, m, Q;int d[N][N];void floyed() { for (int k = 1; k <= n; k++) for (int j = 1; j <= n; j++) for (int i = 1; i > n >> m >> Q; for (int i = 1; i <= n; i++) for (int j = 1; j > a >> b >> w; d[a][b] = min(d[a][b], w); } floyed(); while (Q--) { int a, b; cin >> a >> b; if (d[a][b] > 0x3f3f3f3f / 2) puts("impossible"); else cout << d[a][b] << endl; } return 0;}最小生成树
最小生成树问题99%对应的图都是无向图，正边和负边都可以
- 普利姆算法 Prim
- 朴素版Prim \(O(n^2)\) 稠密图
- 堆优化Prim \(O(mlog_2n)\) 稀疏图，不常用
- 克鲁斯卡尔算法 Kruskal \(O(mlog_2m)\) 稀疏图，常用
Prim
与Dijkstra非常类似，不同的是用 t 更新其他点到集合s的距离，而不是其他点到原点的距离。集合s是当前已经在集合中的点；不在集合内的点，每个点连向集合的边的最短距离，无边为INF
最小生成树的边就是选中 t 时，t 与 集合s之间的边。
858
858. Prim算法求最小生成树 – AcWing题库
#include #include #include #include using namespace std;const int N = 510, INF = 0x3f3f3f3f;int n, m;int g[N][N];int dist[N];bool st[N];int prim() { memset(dist, 0x3f, sizeof dist); int res = 0; for (int i = 0; i < n; i++) { int t = -1; for (int j = 1; j <= n; j++) if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j; if (i && dist[t] == INF) return INF; if (i) res += dist[t]; // ^ 在更新 dist 之前累加，因为有自环问题（-10权重） for (int j = 1; j > n >> m; memset(g, 0x3f, sizeof g); for (int i = 0; i > a >> b >> w; g[a][b] = g[b][a] = min(g[a][b], w); } int t = prim(); if (t == INF) puts("impossible"); else cout << t; return 0;}Kruskal
不需要用邻接表或邻接矩阵存图，只要存每条边（结构体数组）
- 将所有边ab按w重小到大排序（快排）\(O(mlog_2m)\)
- 枚举每条边ab w （相当于并查集简单应用 \(O(m)\)）
- 如果ab不连通，将ab加到集合里面来
859 ⭐
AcWing 859. Kruskal算法求最小生成树 – AcWing
#include #include #include using namespace std;const int N = 2e5 + 10;int n, m;int p[N];struct Edge { int a, b, w; bool operator<(const Edge &W) const { return w > n >> m; for (int i = 0; i > a >> b >> w; edges[i] = {a, b, w}; } sort(edges, edges + m); // ^ 初始化并查集 for (int i = 1; i <= n; i++) p[i] = i; int res = 0, cnt = 0; for (int i = 0; i < m; i++) { int a = edges[i].a, b = edges[i].b, w = edges[i].w; a = find(a), b = find(b); if (a != b) { p[a] = b; res += w; cnt++; } } if (cnt < n - 1) puts("impossible"); else cout << res; return 0;}二分图
- 判断是否二分图：DFS 染色法 \(O(n+m)\)
- 求二分图最大匹配：匈牙利算法 最坏\(O(nm)\)，实际运行时间远小于\(O(nm)\)
染色法
二分图：把所有点划分成两个集合，集合内没有边，集合之间有边；当且仅当图中不含奇数环（环中边的数量是奇数）
可以用 DFS、BFS 模拟染色过程，出现矛盾就不是二分图
860
AcWing 860. 染色法判定二分图 – AcWing
#include #include #include #include using namespace std;const int N = 1e5 + 10, M = 2e5 + 10;int n, m;int h[N], e[M], ne[M], idx;int color[N];void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++;}bool dfs(int u, int c) { color[u] = c; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!color[j]) { if (!dfs(j, 3 - c)) return false; } else if (color[j] == c) return false; } return true;}int main() { cin.tie(0); memset(h, -1, sizeof h); cin >> n >> m; while (m--) { int a, b; cin >> a >> b; add(a, b), add(b, a); } bool flag = true; for (int i = 1; i <= n; i++) { if (!color[i]) { if (!dfs(i, 1)) { flag = false; break; } } } if (flag) puts("Yes"); else puts("No"); return 0;}匈牙利
返回二分图最大匹配（最多的边数，没有两条边共用一个点）
861
861. 二分图的最大匹配 – AcWing题库
#include #include #include #include using namespace std;const int N = 510, M = 1e5 + 10;int n1, n2, m;int h[N], e[M], ne[M], idx;int match[N];bool st[N];void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++;}bool find(int x) { for (int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; if (match[j] == 0 || find(match[j])) { match[j] = x; return true; } } } return false;}int main() { cin.tie(0); memset(h, -1, sizeof h); cin >> n1 >> n2 >> m; while (m--) { int a, b; cin >> a >> b; add(a, b); } int res = 0; for (int i = 1; i <= n1; i++) { memset(st, false, sizeof st); if (find(i)) res++; } cout << res; return 0;}372 ⭐⭐
372. 棋盘覆盖 – AcWing题库
每个卡片塞2个格子，把格子看成点，把卡片看成边，则只要能放卡片的相邻两个格子就连一条边。考虑卡片不会重叠，一定是一个二分图。
二分图最大匹配：匈牙利算法 (男女配对算法 我有多的选择就让给你 你有多的选择就让给我)
#include #include #include #define x first#define y secondusing namespace std;typedef pair PII;const int N = 110;int n, m;PII match[N][N];bool g[N][N], st[N][N];int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};// dfs bool find(int x, int y){ for (int i = 0; i < 4; i ++ )//枚举邻点 { int a = x + dx[i], b = y + dy[i]; if (a && a <= n && b && b > n >> m; while(m--) { int x,y; cin >> x >> y; g[x][y] = true; } memset(match,-1,sizeof match); int res = 0; // 枚举所有和为奇数的点 for(int i=1;i<=n;i++) { for(int j = 1;j<=n;j++) { if((i+j)%2 && !g[i][j]) { memset(st,0,sizeof st);//每次都需要清空st数组，因为匹配好的一对可能会有下家 if(find(i,j))res++;//如果[i,j]能配对 } } } cout << res << endl; return 0;}