第一章 DFS

一、排列数字

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 1

---

2. 思路分析

算法流程：

• 用 $path$ 数组来保存排序，当排序长度为 n 时，是一个排序方案，输出该方案；
• 用 $state$ 数组表示数字是否使用过。当 $state[i]$ 为 1 时表示 $i$已经被使用过， $state[i]$ 为 0 时表示 $i$没有被使用过；
• $dfs(i)$ 表示的含义是：在 $path[i]$ 处填写数字，然后递归的在下一个位置填写数字;
• 回溯：第 i 个位置填写某个数字的所有情况都遍历后， 第 i 个位置填写下一个数字。

---

3. 代码实现

#include <bits/stdc++.h>

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 = 1; i <= n; i ++) printf("%d ", path[i]);
        puts("");
    }
    
    //空位上可以选择的数字 为：1~n
    for (int i = 1; i <= n; i ++)
        if (!st[i]) //如果数字i没有被使用过
        {
            path[u] = i;  //放入空位
            st[i] = true; //数字被用，修改状态
            dfs(u + 1);   //填写下一位
            st[i] = false;//回溯
        }
}

int main()
{
    cin >> n;
    
    dfs(1);
    
    return 0;
}

---

二、n-皇后问题

1. 题目描述

n−皇后问题是指将 n 个皇后放在 $n×n$ 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数 n。

输出格式

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围

$1≤n≤9$

输入样例：

4

输出样例：

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

---

2. 思路分析

• 按行进行枚举搜索，如果该行的第 $i$ 个位置的列、对角线、反对角线没有冲突，则该位置可以防止皇后；
• 当前行如果搜索到了第 $n$ 行，则输出这条路径；
• 每次在搜索下一行的时候，需要进行回溯，恢复现场。

对角线 dg[u+i]dg[u+i]，反对角线udg[n−u+i]udg[n−u+i]中的下标 u+iu+i和 n−u+in−u+i 表示的是截距

• 反对角线 $y=x+b$, 截距 $b=y−x$，因为我们要把 b 当做数组下标来用，显然 b 不能是负的，所以我们加上 $+n$ （实际上+n,+4n,+2n都行），来保证是结果是正的，即 $y - x + n$;
• 而对角线 $y=−x+b$, 截距是 $b=y+x$，这里截距一定是正的，所以不需要加偏移量。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int n;
char g[N][N];
//col列，dg对角线，udg反对角线
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]);
        puts("");
        return;
    }
    
    for (int i = 0; i < n; i ++)
        //i + u 和 i - u是对角线和反对角线的截距，+n是为了保证下标出现负数
        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;
}

---

第二章 BFS

一、走迷宫

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. 思路分析

1. 定义 $g[N][N]$ 来存放地图， $d[N][N]$ 来表示每一个点到起点的距离，用队列来存储要访问的点；
2. 初始化：将每个点到起点的距离设置为-1，表示该点没有被访问过；
3. 从队列中取出队头元素即为要访问的点，枚举该点的上、右、下、左四个方向，如果这四个方向有在边界内的并且是空地还没有被走过的，则将该点到起点的距离加1，并且将新坐标加入队列中；
4. 最后返回右下角到起点的距离即可。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N]; //存放地图
int d[N][N]; //存每一个点到起点的距离

int bfs()
{
    queue<PII> q;
    
    //每个点初始化记录为-1，表示没有走过
    memset(d, -1, sizeof d);
    
    d[0][0] = 0; //表示起点已经走过了
    q.push({0, 0}); //将起点入队
    
    //x 方向的向量和 y 方向的向量组成的上、右、下、左
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        
        //枚举四个方向
        for (int i = 0; i < 4; i ++)
        {
            //x表示沿着此方向走会走到哪个点
            int x = t.first + dx[i], y = t.second + dy[i];
            //在边界内 并且是空地可以走 且之前没有走过
            if (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

输出样例

19

---

2. 思路分析

算法思路：

• 用一个队列保存到当前获取到的状态序列；
• 用一个哈希表保存各个状态到目标状态需要交换的次数；
• 从队列中获取队头元素，从四个方向获取新的状态，如果哈希表中没有这个状态，则将新的状态入队，并且更新哈希表中记录状态的交换次数；
• 如果在得到了目标状态一样的序列，则输出交换次数，结束；
• 如果最后没有得到目标状态，则输出-1 。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

int bfs(string state)
{
    //存字符串的状态
    queue<string> q;
    //将字符串和数字联系在一起，字符串表示状态，数字表示距离
    unordered_map<string, int> d;
    
    q.push(state);
    d[state] = 0;
    
    //定义四个方向
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    //定义目标状态
    string end = "12345678x";
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        
        //如果当前状态与目标状态一致，则返回该状态下的距离
        if (t == end) return d[t];
        
        int distance = d[t]; //记录当前状态的距离
        
        //查找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)
            {
                //转移x
                swap(t[a * 3 + b], t[k]);
                //如果当前状态是第一次遍历，则记录记录并且入队
                if (!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                //还原状态，为下一种状态的转移做准备
                swap(t[a * 3 + b], t[k]);
            }
        }
    }
    //无法转移到目标状态，返回-1
    return -1;
}

int main()
{
    char s[2];
    
    //输入起始状态
    string state;
    for (int i = 0; i < 9; i ++)
    {
        cin >> s;
        state += *s;
    }
    
    cout << bfs(state) << endl;
    
    return 0;
}

---

第三章 树与图的深度优先遍历

一、树的重心

1. 题目描述

给定一颗树，树中包含 n 个结点（编号 $1∼n$）和 $n−1$ 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数 n，表示树的结点数。

接下来 $n−1$ 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式

输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

$1≤n≤10^5$

输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例：

4

---

2. 思路分析

具体的思路见以下的代码注释。

---

3. 代码分析

#include <bits/stdc++.h>

using namespace std;

//以有向图的格式存储无向图，所以每个节点至多对应2n - 2条边
const int N = 100010, M = 2 * N;

int n;
int h[N], e[M], ne[M], idx;
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)
{
    st[u] = true; //标记u节点已经访问过了
    
    int size = 0; //记录u的最大子树的结点数
    int sum = 1;  //记录以u为根的子树的结点数
    
    //访问u的每个子节点
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        //因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
        if(!st[j])
        {
            int s = dfs(j); //s是以j为根的子树的结点数
            size = max(size, s); //记录u的最大子树的结点数
            sum += s; //累加u的各个子树的结点数
        }
    }
    //n-sum 是u上面部分的结点数
    size = max(size, n - sum); // 选择u节点为重心，最大的连通子图节点数
    ans = min(size, ans); //遍历过的假设重心中，最小的最大联通子图的节点数
    
    return sum; //返回以u为根的子树的结点数
}

int main()
{
    cin >> n;
    
    //初始化h数组，-1表示尾节点
    memset(h, -1, sizeof h);
    
    //树中不存在环的，对于有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); //可以任意选择一个节点开始，只要u <= n即可
    
    cout << ans << 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≤10^5$

输入样例：

4 5
1 2
2 3
3 4
1 3
1 4

输出样例：

1

---

2. 思路分析

1. 用 dist 数组来保存各个节点到1号点的距离，初始化为 -1；
2. 从1号点开始进行广度优先遍历，将 1 号点入队，更新 dist[1] == 0;
3. 如果队列非空，则取出队头元素，找到队头所有能到的节点。如果队头能到的点没有访问过，就将该点的 dist 值更新为队头的 dist 值加1，然后入队；
4. 重复步骤 3 直到队列为空；
5. 最后返回 n 号点的 dist 值即可。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m; //n个点m条边
int h[N], e[N], ne[N], idx; //邻接表数据结构
int d[N]; //存储距离

//邻接表存储图
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}


int bfs()
{
    //初始化每个点到起点的距离为-1，表示没有访问过
    memset(d, -1, sizeof d);
    
    queue<int> q;
    d[1] = 0; //从1号点开始，距离为0
    q.push(1); //1号点入队
    
    //队列非空，就一直往后搜索
    while (q.size())
    {
        int t = q.front(); //队头出队，找该点能到的点
        q.pop();
        
        //遍历所有t能到的点
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i]; //通过索引i得到t能到的节点编号
            if (d[j] == -1) //如果该点没有访问过
            {
                d[j] = d[t] + 1;//距离t号节点的距离加1
                q.push(j); //节点入队
            }
        }
    }
    return d[n]; //最后返回n号节点到起点的距离
}

int main()
{
    cin >> n >> m;
    
    //初始化h数组，-1表示尾节点
    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;
}

---

第五章 拓朴排序

一、有向图的拓扑序列

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≤10^5$

输入样例：

3 3
1 2
2 3
1 3

输出样例：

1 2 3

---

2. 思路分析

算法的核心是用队列维护一个入度为0的节点的集合。

1. 初始化，将所有入度为0的点压入队列；
2. 每次从队列中取出队头元素 $x$，将队头 $下、$ 加入数组 $res$;
3. 然后删除 $x$ 所有的出边。所将边 $(x,y)$删除后， $y$ 的入度变为0，则将 $y$ 压入队列；
4. 不断重复步骤2、3过程，知道队列为空；
5. $res$ 数组保存了所有入度为 0 的点，，如果 数组 $res$中的元素个数等于 $n$，则表示该有向图存在拓扑序列。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx; //邻接表存储有向图
int d[N]; //保存各个点的入度
vector<int> res; //保存所有入度为0的点，即拓扑排序

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool topsort()
{
    queue<int> q;
    
    //遍历所有顶点的入度，将入度为0的点加入队列
    for(int i = 1; i <= n; i ++ )
        if(!d[i])
            q.push(i);
    
    //循环队列中的点
    while(q.size())
    {
        int t = q.front();
        q.pop();
        res.push_back(t); //将该点加入拓扑序列
        
        //循环删除t所有的出边
        for(int i = h[t]; i != -1; i = ne[i])
        {
            //删除出边后，j的入度-1，如果入度为0则加入队列
            int j = e[i];
            if(--d[j] == 0) 
                q.push(j);
        }
    }
    //res中的个数等于n，则表示存在拓扑序列
    return res.size() == 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的度 +1
    }
    //不存在拓扑序列，直接输出-1
    if(!topsort()) puts("-1");
    
    else
    {
        //存在拓扑序列，依次输出拓扑序列
        for(int i = 0; i < n; i ++) printf("%d ", res[i]);
        puts("");
    }
    return 0;
}

---

创作不易，如果有帮助到你，请给文章==点个赞和收藏==，让更多的人看到！！！
==关注博主==不迷路，内容持续更新中。