南沙网站制作,网站建设明细报价表,网站该怎么找,株洲最新通告文章目录 前言Part 1#xff1a;DFS#xff08;深度优先遍历#xff09;一、排列数字1.题目描述输入格式输出格式数据范围输入样例输出样例 2.算法 二、n皇后问题1.问题描述输入格式输出格式数据范围输入样例输出样例 2.算法 三、树的重心1.问题描述输入格式输出格式数据范围… 文章目录 前言Part 1DFS深度优先遍历一、排列数字1.题目描述输入格式输出格式数据范围输入样例输出样例 2.算法 二、n皇后问题1.问题描述输入格式输出格式数据范围输入样例输出样例 2.算法 三、树的重心1.问题描述输入格式输出格式数据范围输入样例输出样例 2.算法 Part 2BFS广度优先遍历一、走迷宫1.问题描述输入格式输出格式数据范围输入样例输出样例 2.算法 二、八数码1.题目描述输入格式输出格式输入样例输出样例 2.算法 三、图中点的层次1.题目描述输入格式输出格式数据范围输入样例输出样例 2.算法 Part 3拓扑排序一、有向图的拓扑序列1.题目描述输入格式输出格式数据范围输入样例输出样例 2.算法 前言 本篇博客将介绍DFS-深度优先遍历、BFS-广度优先遍历和拓扑排序的常见题型模板题及其扩展。DFS和BFS是遍历图的两种方法其中BFS多用于求最短路问题在不要求最短时多用DFS因为DFS的复杂度更低。而拓扑排序是图论中一种特殊的问题用于求图中是否存在回路。 Part 1DFS深度优先遍历
一、排列数字
1.题目描述
给定一个整数 n将数字 1∼n 排成一排将会有很多种排列方法。
现在请你按照字典序将所有的排列方法输出。
输入格式
共一行包含一个整数 n。
输出格式
按字典序输出所有排列方案每个方案占一行。
数据范围
1≤n≤7
输入样例
3输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 12.算法 假设有 3 个空位从前往后填数字每次填一个位置填的数字不能和前面一样。最开始的时候三个空位都是空的 __。首先填写第一个空位第一个空位可以填 1填写后为1。填好第一个空位填第二个空位第二个空位可以填 2填写后为1 2 __。填好第二个空位填第三个空位第三个空位可以填 3填写后为 1 2 3。这时候空位填完无法继续填数所以这是一种方案输出。然后往后退一步退到了状态1 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3 没有其他数字可以填。因此再往后退一步退到了状态1 。第二个空位上除了填过的 2还可以填 3。第二个空位上填写 3填写后为1 3 __。填好第二个空位填第三个空位第三个空位可以填 2填写后为 1 3 2。这时候空位填完无法继续填数所以这是一种方案输出。如此反复
#includeiostreamusing namespace std;const int N 10;int path[N];//保存序列
int state[N];//数字是否被用过
int n;void dfs(int u)
{if(u n)//数字填完了输出{for(int i 1; i n; i)//输出方案cout path[i] ;cout endl;}for(int i 1; i n; i)//空位上可以选择的数字为:1 ~ n{if(!state[i])//如果数字 i 没有被用过{path[u] i;//放入空位state[i] 1;//数字被用修改状态dfs(u 1);//填下一个位state[i] 0;//回溯取出 i}}
}int main()
{cin n;dfs(1);
}二、n皇后问题
1.问题描述
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上使得皇后不能相互攻击到即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数 n请你输出所有的满足条件的棋子摆法。
输入格式
共一行包含整数 n。
输出格式
每个解决方案占 n 行每行输出一个长度为 n 的字符串用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后输出一个空行。
注意行末不能有多余空格。
输出方案的顺序任意只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例
4输出样例
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..2.算法 按行枚举回溯剪枝
#include iostreamusing namespace std;const int N 20; // bool数组用来判断搜索的下一个位置是否可行
// col列dg对角线udg反对角线
// g[N][N]用来存路径int n;
char g[N][N];
bool col[N], dg[N], udg[N];void dfs(int u) {// u n 表示已经搜了n行故输出这条路径if (u n) {for (int i 0; i n; i ) puts(g[i]); // 等价于cout g[i] endl;puts(); // 换行return;}// 枚举u这一行搜索合法的列int x u;for (int y 0; y n; y )// 剪枝(对于不满足要求的点不再继续往下搜索) if (col[y] false dg[y - x n] false udg[y x] false) {col[y] dg[y - x n] udg[y x] true;g[x][y] Q;dfs(x 1);g[x][y] .; // 恢复现场col[y] dg[y - x n] udg[y x] false;}
}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;
} 三、树的重心
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输出样例
42.算法
本题的本质是树的dfs 每次dfs可以确定以u为重心的最大连通块的节点数并且更新一下ans也就是说dfs并不直接返回答案而是在每次更新中迭代一次答案用邻接表存储
#include iostream
#include algorithm
#include cstringusing 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;
}//返回以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值不包括根节点4res 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 n - 1; i) {int a, b;cin a b;add(a, b), add(b, a); //无向图}dfs(1); //可以任意选定一个节点开始 uncout ans endl;return 0;
}Part 2BFS广度优先遍历
一、走迷宫
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输出样例
82.算法 从起点开始往前走第一步记录下所有第一步能走到的点然后从所第一步能走到的点开始往前走第二步记录下所有第二步能走到的点重复下去直到走到终点。输出步数即可
#include cstring
#include iostream
#include algorithm
#include queueusing namespace std;typedef pairint, int PII;const int N 110;int n, m;
int g[N][N], d[N][N];//g存储地图d存储距离int bfs()
{queuePII q;memset(d, -1, sizeof d); //距离初始化d[0][0] 0;q.push({0, 0});int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};//BFS宽度优先遍历while (q.size()){auto t q.front();q.pop();//上下左右四种走法for (int i 0; i 4; i ){int x t.first dx[i], y t.second dy[i];//未超过边界x、y的限制且此处可走g是0且未走过d是-1if (x 0 x n y 0 y m g[x][y] 0 d[x][y] -1){d[x][y] d[t.first][t.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;
}二、八数码
1.题目描述
在一个 3×3 的网格中1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。
例如
1 2 3
x 4 6
7 5 8在游戏过程中可以把 x 与其上、下、左、右四个方向之一的数字交换如果存在。
我们的目的是通过交换使得网格变为如下排列称为正确排列
1 2 3
4 5 6
7 8 x例如示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x现在给你一个初始网格请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行将 3×3 的初始网格描绘出来。
例如如果初始网格如下所示
1 2 3
x 4 6
7 5 8 则输入为1 2 3 x 4 6 7 5 8
输出格式
输出占一行包含一个整数表示最少交换次数。
如果不存在解决方案则输出 −1。
输入样例
2 3 4 1 5 x 7 6 8输出样例
192.算法 将 “3*3矩阵” 转化为 “字符串” 二维矩阵下标转化一维字符串下标 最终状态则是“12345678x”
#include iostream
#include algorithm
#include queue
#include unordered_mapusing namespace std;int bfs(string start)
{//定义目标状态string end 12345678x;//定义队列和dist数组queuestring q;//直接存转化后的字符串unordered_mapstring, int d;//将字符串和数字联系在一起字符串表示状态数字表示距离//初始化队列和dist数组q.push(start);d[start] 0;//转移方式int dx[4] {1, -1, 0, 0}, dy[4] {0, 0, 1, -1};while(q.size()){auto t q.front();q.pop();//记录当前状态的距离如果是最终状态则返回距离int distance d[t];if(t end) return distance;//查询x在字符串中的下标然后转换为在矩阵中的坐标int k t.find(x);int x k / 3, y k % 3;for(int i 0; i 4; i){//求转移后x的坐标int a x dx[i], b y dy[i];//当前坐标没有越界if(a 0 a 3 b 0 b 3){//转移xswap(t[k], t[a * 3 b]);//如果当前状态是第一次遍历记录距离入队if(!d.count(t)){d[t] distance 1;q.push(t);}//还原状态为下一种转换情况做准备swap(t[k], t[a * 3 b]);}}}//无法转换到目标状态返回-1return -1;
}int main()
{string c, start;//输入起始状态for(int i 0; i 9; i){cin c;start c;}cout bfs(start) endl;return 0;
}三、图中点的层次
1.题目描述
给定一个 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输出样例
12.算法
邻接表存储的BFS思路与前面完全一致
#include iostream
#include cstring
#include algorithm
#include queue
using namespace std;const int N 100010;int h[N],ne[N], e[N], idx;//邻接表数据结构
int dist[N];//存储距离
int st[N];//标记点是否走到过
int n, m;void add(int a, int b)//邻接表存储图
{e[idx] b, ne[idx] h[a], h[a] idx;
}void bfs()
{memset(dist, 0x3f, sizeof(dist));//初始都没有走到过距离无穷大dist[1] 0;//从1号节点开始距离为0queueint q;//队列q.push(1);//1号节点入队列st[1] 1;//1到1的距离为0已经求出while(q.size())//对列非空就一直往后搜索{int t q.front();//队头出队找该点能到的点q.pop();for(int i h[t]; i ! -1; i ne[i])//遍历所有t节点能到的点i为节点索引{int j e[i];//通过索引i得到t能到的节点编号if(!st[j])//如果没有遍历过{dist[j] dist[t] 1;//距离为t号节点的距离1q.push(j);//节点入队st[j] 1;//入队后标记已经遍历过了}}}
}int main()
{cin n m;memset(h, -1, sizeof h);//初始化所有节点没有后继后继都是-1for(int i 0; i m; i)//读入所有边{int a, b;cin a b;add(a, b);//加入邻接表}bfs();//广度优先遍历cout (dist[n] 0x3f3f3f3f ? -1 : dist[n]);//如果到n号节点的距离不是无穷大输出距离如果是无穷大输出-1.return 0;
}Part 3拓扑排序
一、有向图的拓扑序列
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 32.算法
什么是拓扑排序一个有向图如果图中有入度为 0 的点就把这个点删掉同时也删掉这个点所连的边。一直进行此处理如果所有点都能被删掉则这个图可以进行拓扑排序。首先记录各个点的入度然后将入度为 0 的点放入队列将队列里的点依次出队列然后找出所有出队列这个点发出的边删除边同事边的另一侧的点的入度 -1。如果所有点都进过队列则可以拓扑排序输出所有顶点。否则输出-1代表不可以进行拓扑排序。
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 100010;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int q[N], hh 0, tt -1;//队列保存入度为0的点也就是能够输出的点
int n, m;//保存图的点数和边数
int d[N];保存各个点的入度void add(int a, int b){e[idx] b, ne[idx] h[a], h[a] idx;
}void topsort(){for(int i 1; i n; i){//遍历一遍顶点的入度。if(d[i] 0)//如果入度为 0, 则可以入队列q[tt] i;}while(tt hh){//循环处理队列中点的int a q[hh];for(int i h[a]; i ! -1; i ne[i]){//循环删除 a 发出的边int b e[i];//a 有一条边指向bd[b]--;//删除边后b的入度减1if(d[b] 0)//如果b的入度减为 0,则 b 可以输出入队列q[tt] b;}}if(tt n - 1){//如果队列中的点的个数与图中点的个数相同则可以进行拓扑排序for(int i 0; i n; i){//队列中保存了所有入度为0的点依次输出cout q[i] ;}}else//如果队列中的点的个数与图中点的个数不相同则可以进行拓扑排序cout -1;//输出-1代表错误
}int main(){cin n m;//保存点的个数和边的个数memset(h, -1, sizeof h);//初始化邻接矩阵while (m -- ){//依次读入边int a, b;cin a b;d[b];//顶点b的入度1add(a, b);//添加到邻接矩阵}topsort();//进行拓扑排序return 0;
}
