前言
本专栏文章为本人AcWing算法基础课的学习笔记，课程地址在这。如有侵权，立即删除。
课前温习
一、深度优先搜索（DFS）
特点：尽可能先向纵深方向搜索。使用stack实现。所需空间O(h)（h为深度）。不具有“最短性”。
1、排列数字
题目链接：842. 排列数字
1.1题目描述
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。现在，请你按照 字典序 将所有的排列方法输出。
输入格式
共一行，包含一个整数 n 。
输出格式
按字典序输出所有排列方案，每个方案占一行。
数据范围
1≤n≤7
输出样例：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
1.2思路分析
dfs 注意 顺序，为树形结构遍历，形式如图。
2.回溯时，需 恢复现场。
1.3代码实现
#include <iostream> using namespace std; const int N =10; int n; int path[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;i++){ //如果当前数没被用过 if(!st[i]){ path[u]=i; //把数字填到当前位置 st[i]=true; //记录数字已被用过 dfs(u+1); //处理完后走到下一层 st[i]=false; //恢复现场 } } } int main() { cin>>n; dfs(0); return 0; }
2、 n-皇后问题
题目链接：843. n-皇后问题
1.4题目描述
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即 任意两个皇后都不能处于同一行、同一列或同一斜线 上。
现在给定整数 n，请你输出所有的 满足条件的棋子摆法。
输入格式
共一行，包含整数 n。
输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例：
4
1
输出样例：
.Q.. ...Q Q... ..Q. ..Q. Q... ...Q .Q..
1.5思路分析
思路1：按照上题思路，（枚举每一行的皇后应该放到哪个位置（每行一个皇后））然后进行减枝。
（每条对角线）
思路2：
枚举每个格子是否放皇后,每次都有两种选择，放或者不放，当到枚举到第n行第n列结束。
1.6代码实现
思路1代码：
#include <iostream> using namespace std; const int N =20; int n; char g[N][N]; //记录方案 bool col[N],dg[N],udg[N]; //记录列、正对角线、反对角线是否出现过 void dfs(int u){ //找到一种方案输出 if(u==n){ for(int i=0;i<n;i++){ cout<<g[i]<<endl; } cout<<endl; return ; } //枚举每一列，看皇后可放在哪一列 for(int i=0;i<n;i++){ //如果列、正对角线、副对角线没有出现过 //对角利用一次函数截距，y=-x+b,则b=y+x;y=x+b,则b=y-x,（本题可视为x为行下标，y为列下标，第一行为x轴，第一列为y轴，而每两条匹配的正副对角线，与y轴截距相同，可以据此来已有一条对角线的前提下，找出它的正/副对角线）因下标不为负数，此情况需要将每个副对角线加一个正数保证下标为正，正数随便加，但也不能使数组下标越界。 if(!col[i]&&!dg[u+i]&&!udg[n-u+i]){ g[u][i]='Q'; col[i]=dg[u+i]=udg[n-u+i]=true; dfs(u+1); col[i]=dg[u+i]=udg[n-u+i]=false; g[u][i]='.'; } } } int main() { cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ g[i][j]='.'; } } dfs(0); return 0; }
思路2代码：
#include <iostream> using namespace std; const int N =20; int n; char g[N][N]; //记录方案 bool row[N],col[N],dg[N],udg[N]; //记录行、列、正对角线、反对角线是否出现过 void dfs(int x,int y,int s){ //x,y代表格子坐标，s代表皇后个数 //如果已出界，则将格子转到下一行第一个 if(y==n){ y=0; x++; } if(x==n){ //如果皇后数量为n，则是一种方案，输出 if(s==n){ for(int i=0;i<n;i++){ cout<<g[i]<<endl; } cout<<endl; } return ; //注意return位置，当x越界，无论是否是一种方案，均返回，结束搜索 } //不放皇后 dfs(x,y+1,s); //放皇后 if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n]){ g[x][y]='Q'; row[x]=col[y]=dg[x+y]=udg[x-y+n]=true; dfs(x,y+1,s+1); row[x]=col[y]=dg[x+y]=udg[x-y+n]=false; g[x][y]='.'; } } int main() { cin>>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(2h)（h为深度）。具有“最短性”(边权都为1时，可以用BFS求最短路)。
1、走迷宫
题目链接：844. 走迷宫
2.1题目描述
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人 从左上角移动至右下角 (n,m) 处，至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例：
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
输出样例：
8
2.2思路分析
利用宽搜进行模拟，具体看代码注释部分。
(若要输出路径只需要记录每个点的前一个点，即在入队之前将该点记录下来，如下y总代码，Prev数组便是来记录点是由哪个点转移来)
2.3代码实现
#include <iostream> #include <string.h> #include <queue> using namespace std; typedef pair<int,int> PII; const int N=110; int n,m; int g[N][N]; //存储迷宫地图 int d[N][N]; //每个点到起点的距离 queue<PII> q; int bfs(){ q.push({0,0}); memset(d,-1,sizeof d); //初始化距离均为-1，代表每个点没有被走过 (代替了标记数组) d[0][0]=0; //利用方向数组模拟上下左右四个点 int dx[]={-1,0,1,0}; int dy[]={0,1,0,-1}; while(!q.empty()){ PII temp=q.front(); q.pop(); for(int i=0;i<4;i++){ int x=temp.first+dx[i],y=temp.second+dy[i]; //每次循环x,y代表周围的点 //如果点在界内且该点可走且该点没有被走过，将这个点计入路径 if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1){ d[x][y]=d[temp.first][temp.second]+1; q.push({x,y}); } } } return d[n-1][m-1]; } int main() { cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>g[i][j]; } } cout<<bfs()<<endl; return 0; }
三、树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。
两种存储方式：
(1）邻接矩阵：g[a][b] 存储边a->b
(2）邻接表
//对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点。
int h[N],e[M],ne[M],idx; /*idx代表边的下标索引（编号） h[N]存储N个链表的头结点（第一条边的idx） e[M]存储第idx条边终点的值 ne[M]存储第idx条边 同起点的下一条边的编号（idx） idx表示当前边的编号 */ //添加一条边a->b void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } //初始化 idx=0; memset(h,-1,sizeof h);
四、树与图的遍历
1、深度优先遍历（846. 树的重心）
核心模板
时间复杂度：O(n+m),n表示点数，m表示边数。
int dfs(int u){ st[u]=true; //stu[u]表示点u已经被遍历过 for(int i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(!st[j]) dfs(j); } }
题目链接：846. 树的重心
4.1题目描述
给定一颗树，树中包含 n 个结点（编号1∼n）和 n−1条无向边。请你找到 树的重心，并输出将重心删除后，剩余各个连通块中 点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 n，表示树的结点数。
接下来 n−1行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。
输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
1≤n≤105
输入样例：
9 1 2 1 7 1 4 2 8 2 5 4 3 3 9 4 6 1
4.2思路分析
依次对于每个点，并分别求出删除该点后各个连通块中点数的最大值，然后针对求出来的每个最大值，再取最小值，即为答案。
通过深度优先遍历求每个子树中点的个数，而子树的子树可以递归求解，对于子树的上面部分的连通块中点的个数直接用总数减去子树的点数即可。
4.3代码实现
#include <iostream> #include <string.h> using namespace std; const int N=100010,M=N*2; //N代表点，M代表边 int h[N],e[M],ne[M],idx; int n; bool st[N]; //标记点是否处理/出现过 int ans=N; //记录答案 /* idx表示边的编号 h数组存储每个结点的第一条边的idx e数组存储第idx条边的终点 ne数组存储以第idx条边的起点为起点的第idx条边的下一条边 */ void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } //以u为根的子树中点的数量 int dfs(int u){ st[u]=true; //标记u已经被搜过 int sum=1,res=0; //sum代表当前子树的大小(结点个数)，res代表删除点以后连通块中点数的最大值 for(int i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(!st[j]){ int s=dfs(j); //s代表当前子树的大小 res=max(res,s); //当前子树中点的数量也要在总连通块中点的数量取max sum+=s; //当前子树是以u为根结点子树的一部分，以u结点为根子树中结点的数量要加上这部分 } } res=max(n-sum,res); //n-sum代表除以u为根结点的子树外，剩余部分（上部分）所组成连通块中点的数量 ans=min(ans,res); //答案是连通块中点的数量最大值中的最小值 return sum; } int main() { cin>>n; memset(h,-1,sizeof h); for(int i=0;i<n-1;i++){ int a,b; cin>>a>>b; add(a,b),add(b,a);//无向边需添加两条边 } dfs(1); cout<<ans<<endl; return 0; }
2、宽度优先遍历（847. 图中点的层次）
时间复杂度：O(n+m),n表示点数，m表示边数。
核心模板
queue<int>q; st[1]=true; //表示1号点已经被遍历过 q.push(1); while(q.size()){ int t=q.front(); q.pop(); for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(!st[j]){ st[j]=true;//表示点j已经被遍历过 q.push(j); } } }
题目链接：847. 图中点的层次
4.4题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。
所有边的长度都是 1，点的编号为 1∼n。
请你求出 1 号点到 n 号点的 最短距离，如果从 1 号点无法走到 n 号点，输出 −1。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
数据范围
1≤n,m≤105
输入样例：
4 5 1 2 2 3 3 4 1 3 1 4
输出样例：
1
4.5思路分析
基本框架
4.6代码实现
可手写队列，也可直接使用stl内置队列。
使用STL内置队列代码
#include <iostream> #include <string.h> #include <queue> using namespace std; const int N=100010; int h[N],e[N],ne[N],idx; int n,m; int d[N]; queue<int> q; void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } int bfs(){ q.push(1); memset(d,-1,sizeof d); d[1]=0; while(!q.empty()){ int t=q.front(); q.pop(); for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(d[j]==-1){ q.push(j); d[j]=d[t]+1; } } } return d[n]; } int main() { int a,b; memset(h,-1,sizeof h); cin>>n>>m; for(int i=0;i<m;i++){ cin>>a>>b; add(a,b); } cout<<bfs(); return 0; }
手写模拟队列代码
#include <iostream> #include <string.h> using namespace std; const int N=100010; int h[N],e[N],ne[N],idx; int n,m; int d[N],q[N];//d[]代表距离，q[]模拟队列 /* idx表示边的编号 h数组存储每个结点的第一条边的idx e数组存储第idx条边的终点 ne数组存储以第idx条边的起点为起点的第idx条边的下一条边 */ void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int bfs(){ int hh=0,tt=0; //定义队头和队尾 q[0]=1; memset(d,-1,sizeof d); //初始化都为-1代表都没被遍历过（代替了标记数组） d[1]=0; while(hh<=tt){ int t=q[hh++]; //t每次取队头元素 //遍历t的所有相邻点 for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; //j代表当前点 if(d[j]==-1){ //如果当前点没被遍历过 d[j]=d[t]+1; //到达j点的距离为到达t点的距离+1 q[++tt]=j; //队尾插入j } } } return d[n]; } int main() { cin>>n>>m; memset(h,-1,sizeof h); for(int i=0;i<m;i++){ int a,b; cin>>a>>b; add(a,b); } cout<<bfs()<<endl; return 0; }
五、拓扑排序（848. 有向图的拓扑序列）
有向无环图称为拓扑图，拓扑序列满足：如果存在vi到vj的路径，则顶点vi必然在顶点vj之前。
核心模板
时间复杂度：O(n+m)，n表示点数，m表示边数。
bool tp(){ int hh=0,tt=-1; //d[i]存储点i的入度 for(int i=1;i<=n;i++){ if(!d[i]){ q[++tt]=i; } } while(hh<=tt){ int t=q[hh++]; for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(--d[j]==0){ q[++tt]=j; } } } //如果所有点都入队了，说明存在拓扑序列；否在不存在拓扑序列。 return tt==n-1; }
题目链接：848. 有向图的拓扑序列
5.1题目描述
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。
请输出任意一个该有向图的 拓扑序列，如果拓扑序列不存在，则输出 −1。
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。
输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。否则输出 −1。
数据范围
1≤n,m≤105
输入样例：
3 3 1 2 2 3 1 3
输出样例：
1 2 3
5.2思路分析
一个有向无环图至少存在一个入度为0的点。
所有入度为0的点都可作为最开始的点，将它们入队。
然后枚举队头的每条出边，并且删掉（因为队头点已在拓扑序列第一个点），来找下一个入度为0的点，然后入队。
如果所有点都入队了，说明存在拓扑序列；否在不存在拓扑序列。队列元素顺序即为拓扑序列。
5.3代码实现
y总手动模拟队列代码
我的代码
注：不能像y总那样直接输出队列即为答案的原因：因为y总的手写队列可以访问队头已出队元素，而STL中queue不能，所以需要将答案记录下来。
#include <iostream> #include <cstring> #include <queue> using namespace std; const int N=100010; int h[N],e[N],ne[N],idx; int n,m; int d[N],ans[N],num;//d[]代表点的入度,ans为结果数组 ,num代表结果数组的长度 queue<int> q; /* idx表示边的编号 h数组存储每个结点的第一条边的idx e数组存储第idx条边的终点 ne数组存储以第idx条边的起点为起点的第idx条边的下一条边 */ void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool tp(){ for(int i=1;i<=n;i++){ //如果入度为0，则入队 if(!d[i]){ q.push(i); } } while(!q.empty()){ int t=q.front(); //取队头元素 q.pop(); ans[num++]=t; //遍历队头元素的每个邻点 for(int i=h[t];i!=-1;i=ne[i]){ //找到队头元素出边的终点 int j=e[i]; //删掉出边 d[j]--; //如果删完后j入度为0，则也入队 if(d[j]==0){ q.push(j); } } } //所有点都入队才存在拓扑序列 return num==n; } int main() { cin>>n>>m; memset(h,-1,sizeof h); for(int i=0;i<m;i++){ int a,b; cin>>a>>b; add(a,b); d[b]++; //每多一条指向b的边，b的入度加1 } if(tp()){ for(int i=0;i<n;i++){ cout<<ans[i]<<" "; } } else{ cout<<-1; } return 0; }
