深度优先遍历与回溯算法

排列数字

题干

给定一个整数 ，将数字 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

输入样例

1
3

输出样例

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

思路分析

本题考查深度优先遍历（DFS）和回溯算法。通过递归地选择数字，标记已使用的数字，构造排列，最终输出所有排列方案。

不妨设我们用 path 数组存储当前排列方案，用 st 数组标记数字是否被使用过；dfs(u)表示当前已经排列了 u-1 个数字，接下来需要排列第 u 个数字。

  1. 递归终止条件：当 u > n 时，说明已经排列完所有数字，输出当前 path 数组中的排列方案。
  2. 递归过程：
    • 遍历数字 1 到 n，检查数字 i 是否被使用过（即 used [i] 是否为 true）。
    • 如果数字 i 未被使用过，则将其加入当前排列方案 path [u]，并将 used [i] 标记为 true。
    • 递归调用 dfs(u+1)以排列下一个数字。
    • 回溯时，将 used [i] 重新标记为 false，以便在后续的排列中使用该数字。
    • 时间复杂度为 O(n*n!)，空间复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const int N = 10;

int n;
int path[N];
bool used[N];

void dfs(int u) // u表示当前正在处理第几个数（即已经填了u-1个数）
{
    if (u == n + 1)
    {
        for (int i = 1; i <= n; i++)
            cout << path[i] << ' ';
        cout << '\n';
        return;
    }
    // 如果到第n+1层，也就是填完了，就打印
    for (int i = 1; i <= n; i++)
    {
        if (!used[i])
        {
            path[u] = i;
            used[i] = true;
            dfs(u + 1);
            used[i] = false;
        }
        // 找到还没有被用的数，下一层填它，然后递归dfs(u+1)；递归完回溯要恢复原样，把这个数再改回没被使用
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    dfs(1);
}

n-皇后问题

题干

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

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

输入格式

共一行，包含整数 。

输出格式

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

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

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

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

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

数据范围

输入样例

1
4

输出样例

1
2
3
4
5
6
7
8
9
10
.Q..
...Q
Q...
..Q.

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

思路分析

如果不考虑对角线的限制，我们要在 n 行各放置一个皇后，并且每列只能放置一个皇后，这相当于求 1 到 n 的全排列问题，和上一题类似。但是本题要考虑对角线问题，也就是说我们不仅要用一个 column 数组来标记每一列是否有皇后，还需要用两个对角线数组来标记每一条对角线上是否有皇后。

设 表示第 i 列是否有皇后， 数组表示从左上到右下的对角线是否有皇后， 数组表示从右上到左下的对角线是否有皇后；对于行号为 u，列号为 i 的格子，其对应的两条对角线编号分别为 （主对角线）和 （副对角线），因此我们可以通过检查 、 和 来判断该位置是否可以放置皇后。（不需要在意常数，因为都是加减同一个常数，只需要确定行列之间的加减关系即可）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 12, M = 2 * N;

int n;
bool column[N], dg[M], udg[M];
char res[N][N];

void dfs(int u) // dfs(u)表示u-1行已经处理完毕，正在处理第u行
{
    if (u == n + 1)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                cout << res[i][j];
            cout << '\n';
        }
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!column[i] && !dg[u - i + n] && !udg[u + i])
        {
            column[i] = dg[u - i + n] = udg[u + i] = true;
            res[u][i] = 'Q';
            dfs(u + 1);
            res[u][i] = '.';
            column[i] = dg[u - i + n] = udg[u + i] = false;
        }
        // !column[i]表示第i列没填过
        // !dg[u - i + n]表示主对角线，由于主对角线斜率为1（左上角为[1][1]，右下角[n][n]），因此横纵坐标差为定值
        // 由于u-i不一定是正数，所以加上n（dg数组不一定要从dg[0]或者dg[1]开始用，只要同一个对角线的是同一值就行了）
        // !udg[u + i]表示副对角线，斜率为-1所以横纵坐标和为定值，u+i必为正数所以不需要+n
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            res[i][j] = '.';
    // 初始化
    dfs(1);
}

广度优先遍历

走迷宫

题干

给定一个 的二维整数数组，用来表示一个迷宫，数组中只包含 或 ，其中 表示可以走的路， 表示不可通过的墙壁。

最初，有一个人位于左上角 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 处，至少需要移动多少次。

数据保证 处和 处的数字为 ，且一定至少存在一条通路。

输入格式

第一行包含两个整数 和 。

接下来 行，每行包含 个整数（ 或 ），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

输入样例

1
2
3
4
5
6
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

输出样例

1
8

思路分析

本题考查广度优先遍历（BFS）算法。BFS 适用于在无权图中寻找最短路径的问题。我们可以将迷宫视为一个图， 表示可以通行的节点， 表示不可通行的节点。通过 BFS，我们可以逐层扩展搜索范围，直到找到目标位置。

BFS 的基本步骤如下：

  1. 初始化队列，将起始位置 入队，并标记为已访问。
  2. 定义四个方向的移动向量，表示上下左右的移动。
  3. 开始循环，直到队列为空：
    • 取出队首元素，检查是否为目标位置 ，如果是则输出当前步数并结束。
    • 否则，遍历四个方向，计算新的位置 。
    • 检查新位置是否合法，如果合法则将其入队，并标记为已访问，同时记录步数为上一步+1。
  4. 如果队列为空且未找到目标位置，说明无法到达目标位置；如果找到目标位置，输出移动次数即可。
  5. 时间复杂度为 ，空间复杂度为 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110, M = N * N;

int mp[N][N], dist[N][N]; // 存储地图和距离
int n, m;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};

PII que[M]; // 队列，存储坐标对
int hh = 1, tt = 0; // 队列头尾指针

void bfs(int a, int b)
{
    que[++tt] = {a, b};
    dist[a][b] = 0;
    while (hh <= tt)
    {
        PII t = que[hh++];
        int x = t.first, y = t.second;
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if (mp[xx][yy] == 0 && xx >= 1 && xx <= n && yy >= 1 && yy <= m)
            {
                dist[xx][yy] = dist[x][y] + 1;
                mp[xx][yy] = 1;
                que[++tt] = {xx, yy};
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    memset(dist, -1, sizeof dist); // 初始化距离数组为-1，如果某个位置dist仍为-1，表示该位置未被访问过
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];
    bfs(1, 1);
    cout << dist[n][m];
}

八数码

题干

在一个 的网格中， 这 个数字和一个 x 恰好不重不漏地分布在这 的网格中。

例如：

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

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

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

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1
2
3
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

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式

输入占一行，将 的初始网格描绘出来。

例如，如果初始网格如下所示：

1
2
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

输出样例

1
19

思路分析

本题考查 BFS 在状态空间搜索中的应用。我们可以将每一个网格状态视为图中的一个节点，通过交换 x 与相邻数字来生成新的状态节点。BFS 能够帮助我们找到从初始状态到目标状态的最短路径。

如何将网格状态转化为节点？我们可以将网格中的数字按行优先顺序拼接成一个字符串，例如上面的初始状态可以表示为 "23415x768"，目标状态为 "12345678x"。这类网格转化为字符串的问题，我们一般使用 0-base 数组，这样的好处是：

将二维数组下标 转化为一维数组下标 ；
将一维数组下标 转化为二维数组下标 ，其中 ，。

如何记录一个字符串已经出现过？我们可以用 unordered_map 来存储每个状态字符串及其对应的相对原状态的交换次数，如果 unordered_map 中不存在该字符串，说明该状态未被访问过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;

unordered_map<string, int> dist;
int n, m;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};

string que[N];
int hh = 1, tt = 0;

string ed = "12345678x";

int bfs(string s)
{
    que[++tt] = s;
    dist[s] = 0;
    while (hh <= tt)
    {
        string u = que[hh++];
        if (u == ed)
            return dist[u];
        int idx = u.find('x');
        int x = idx / 3, y = idx % 3, distance = dist[u];
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx >= 0 && xx <= 2 && yy >= 0 && yy <= 2)
            {
                swap(u[idx], u[xx * 3 + yy]);
                if (!dist.count(u))
                {
                    dist[u] = distance + 1;
                    que[++tt] = u;
                }
                swap(u[idx], u[xx * 3 + yy]);
            }
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string st;
    for (int i = 0; i < 9; i++)
    {
        char c;
        cin >> c;
        st += c;
    }
    cout << bfs(st);
}

树与图的深度优先遍历

在介绍题目之前，我们先回忆如何存储树和图。常用的方法有邻接矩阵和邻接表两种。

  • 邻接矩阵：使用一个二维数组 g[][] 来存储图的信息，如果点 a 和点 b 之间有边相连，则 g[a][b] = 1，否则为 0。邻接矩阵适用于边较多的图（稠密图），但空间复杂度较高，为 。
  • 邻接表：使用一个数组 h[] 来存储每个点的边表，边表通过链表或动态数组来存储与该点相连的所有点。邻接表适用于边较少的图（稀疏图），空间复杂度为 ，其中 是边的数量。

邻接表模板(1-base)：

1
2
3
4
5
6
7
8
9
const int N = 1e5 + 10;
int h[N], e[N * 2], ne[N * 2], idx = 1;

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

树的重心

题干

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

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

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

输入格式

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

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

输出格式

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

数据范围

输入样例

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

输出样例

1
4

思路分析

本题考查树的 DFS 算法。对于一棵树，将一个结点删除后，这个结点的子结点会分别成为不同的连通块，而该结点的父结点所在的连通块则包含除该结点子树外的其他结点。因此，我们需要计算每个结点删除后各个连通块的大小，并找出其中的最大值。

首先我们可以用 DFS 计算出每个结点的子树大小。得到每个结点的子树大小后，我们可以遍历删除该结点后连通块大小的最大值。具体步骤如下：

  1. 使用邻接表存储树的边。
  2. 使用 DFS 计算每个结点的子树大小。
  3. 对于每个结点，计算删除该结点后各个连通块的大小，找出最大值。
  4. 找出所有结点中最大连通块大小的最小值，即为树的重心对应的答案。
  5. 时间复杂度为 ，空间复杂度为 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;

int h[N], e[M], ne[M], idx = 1, n;
bool st[N];
int son[N]; // son[i]表示i结点有多少子结点（含自身）

// 默认以结点1为根

int min_max = 1e9; // min_max表示连通块数量最大值的最小值

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

void dfs(int u)
{
    if (st[u])
        return;
    st[u] = true;
    son[u] = 1;
    int mx = 0; // mx 表示去掉点u后连通块数量的最大值
    for (int i = h[u]; i; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) // 防止其往父结点遍历
        {
            dfs(j);
            son[u] += son[j];
            mx = max(mx, son[j]);
            // 遍历子结点并求出子结点连通块的值，与当前连通块最大值取大
        }
    }
    mx = max(mx, n - son[u]);
    // 最后计算除开u的子树外的连通块数量，取大，此时mx即为连通块最大值
    min_max = min(min_max, mx); // 与去掉u的连通块最大值取小
}

int main()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs(1);
    cout << min_max;
}

树与图的广度优先遍历

图中点的层次

题干

给定一个 个点 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 ，点的编号为 。

请你求出 号点到 号点的最短距离，如果从 号点无法走到 号点，输出 。

输入格式

第一行包含两个整数 和 。
接下来 行，每行包含两个整数 和 ，表示存在一条从 走到 的长度为 1 的边。

输出格式

输出一个整数，表示 号点到 号点的最短距离。

数据范围

输入样例

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

输出样例

1
1

思路分析

本题考查广度优先遍历（BFS）算法在有向图中的应用。由于本题点和边是同一个数量级，属于稀疏图，因此用邻接表来存。

由于是无权图，因此先搜索到的路径一定是最短路径，不存在后搜索到的更短，要更新已经求出来的路径的情况，因此所有点判断是否访问过即可，访问过不入队，未访问过入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int h[N], e[N], ne[N], dist[N], idx = 1, n, m;
int que[N], hh = 1, tt = 0;


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

void bfs(int u)
{
    que[++tt] = u;
    dist[u] = 0;
    while (hh <= tt)
    {
        int t = que[hh++];
        for (int i = h[t]; i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] == -1)
            {
                dist[j] = dist[t] + 1;
                que[++tt] = j;
            }
        }
    }
}


int main()
{
    cin >> n >> m;
    memset(dist, -1, sizeof dist);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    bfs(1);
    cout << dist[n];
}

拓扑排序

有向图的拓扑序列

题干

给定一个 个点 条边的有向图，点的编号是 到 ，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 。

若一个由图中所有点构成的序列 满足：对于图中的每条边 ， 在 中都出现在 之前，则称 是该图的一个拓扑序列。

输入格式

第一行包含两个整数 和 。
接下来 行，每行包含两个整数 和 ，表示存在一条从点 到点 的有向边 。

输出格式

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 。

数据范围

输入样例

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

输出样例

1
1 2 3

思路分析

本题考查拓扑排序算法。拓扑排序适用于有向无环图（DAG），用于线性排序图中的节点，使得对于每条有向边 ，节点 在节点 之前。如果是有环图，则不存在拓扑序列。

我们可以使用入度数组和 BFS 来实现拓扑排序。具体步骤如下：

  1. 使用邻接表存储图的边，同时维护一个入度数组 in[]，记录每个节点的入度。
  2. 将所有入度为 的节点入队。
  3. 开始循环，直到队列为空：
    • 取出队首节点，将其加入拓扑序列。
    • 遍历该节点的所有邻接节点，将它们的入度减 ，如果某个邻接节点的入度变为 ，则将其入队。
    • 记录已加入拓扑序列的节点数量。
    • 如果最终加入拓扑序列的节点数量等于 ，则输出拓扑序列；否则输出 ，表示图中存在环。
    • 时间复杂度为 ，空间复杂度为 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

bool st[N];
int h[N], e[N], ne[N], in_degree[N], idx = 1;
int n, m;

int que[N], hh = 1, tt = 0;

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

void top_sort()
{
    // 初始化队列，将所有入度为0的点入队
    for (int i = 1; i <= n; i++)
        if (!in_degree[i])
            que[++tt] = i;
    while (hh <= tt)
    {
        int t = que[hh++];
        for (int i = h[t]; i; i = ne[i])
        {
            int j = e[i];
            st[j] = true;
            in_degree[j]--;
            // 每遍历到一个点，就将其入度减1
            if (!in_degree[j])
            	que[++tt] = j;
            // 如果入度变为0，就将其入队
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        in_degree[b] += 1;
    }
    top_sort();
    if (tt == n)
    	for (int i = 1; i <= n; i++)
    		cout << que[i] << ' ';
    else
    	cout << -1;
}

最短路算法

image-20251206112616781

注意：写最短路算法的时候一定要记得初始化！！！！

邻接矩阵初始化为大数，距离数组 dist 初始化为大数

同时将 dist 起点设为 0

Dijkstra

Dijkstra 求最短路 I

题干

给定一个 个点 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 号点到 号点的最短距离，如果无法从 号点走到 号点，则输出 −1。

输入格式

第一行包含整数 和 。

接下来 行每行包含三个整数 ，表示存在一条从点 到点 的有向边，边长为 。

输出格式

输出一个整数，表示 号点到 号点的最短距离。
如果路径不存在，则输出 。

数据范围

,
,
图中涉及边长均不超过 10000。

输入样例

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

输出样例

1
3

思路分析

Dijkstra 算法适用于边权为非负值的图，用于求解单源最短路径问题。该算法通过贪心策略，逐步扩展已知最短路径的节点集合，直到找到目标节点的最短路径。具体步骤如下：

  1. 使用邻接矩阵存储图的边，同时维护一个距离数组 dist[]，初始化为无穷大，起点距离设为 。
  2. 使用一个布尔数组 st[] 来标记节点距离是否已被确定。
  3. 每次从未确定的节点中选出距离起点最近的节点，更新其邻接节点的距离。
  4. 重复步骤 3，直到所有节点都被访问或无法继续扩展。
  5. 最终 dist[n] 即为从 1 号点到 n 号点的最短距离，如果为无穷大，则输出 。

由于一次循环可以确定一个点的距离，因此需要 n-1 次循环；每次循环内部需要找到未确定节点的最小距离点，需要 n 次循环；最后用这个点更新所有邻接点的距离，需要 n 次循环。读入数据需要 m 次循环。因此总时间复杂度为 O(n^2 + m)，空间复杂度为 O(n + m)。

注意：由于一开始将 dist 数组初始化为大数，并且邻接矩阵也初始化为大数，因此无需判断两个点是否有边相连，直接用 min 函数更新即可。
由于有重边和自环，因此在读入数据时需要取边长的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
const int N = 510;

int n, m;
int edge[N][N], dist[N];
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 1; i <= n; i++)
    {
        // 找到未确定的点中距离起点最近的点
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
            	t = j;
        st[t] = true;
        // 用该点更新其他点的距离
        for (int j = 1; j <= n; j++)
        	dist[j] = min(dist[j], dist[t] + edge[t][j]);
    }
    if (dist[n] > 0x3f3f3f3f / 2) // 如果距离大于一个较大的数，说明不可达（用大于较小的大数而不是等于是好习惯）
    	return -1;
    return dist[n];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;

    memset(edge, 0x3f, sizeof edge);

    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        edge[x][y] = min(edge[x][y], z);
    }
    cout << dijkstra();
    return 0;
}

Dijkstra 求最短路 II

题干

给定一个 个点 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 号点到 号点的最短距离，如果无法从 号点走到 号点，则输出 −1。

输入格式

第一行包含整数 和 。

接下来 行每行包含三个整数 ，表示存在一条从点 到点 的有向边，边长为 。

输出格式

输出一个整数，表示 号点到 号点的最短距离。
如果路径不存在，则输出 。

数据范围

图中涉及边长均不小于 ，且不超过 。

数据保证：如果最短路存在，则最短路的长度不超过

输入样例

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

输出样例

1
3

思路分析

本题考查堆优化版的 Dijkstra 算法。观察朴素 Dijkstra 算法的时间复杂度为 ，当 较大时效率较低。发现最慢的一步是找到未确定的节点中距离起点最近的节点，这一步可以通过使用优先队列（最小堆）来优化；此时插入操作将变为 的时间复杂度，因此总时间复杂度将降低为 。

注意：由于是稀疏图，因此用邻接表存储数据，此时就不需要确保重边一定是最短的，因为在遍历邻接表时会自动更新成最短路径；由于堆中需要保留距离和节点编号，因此可以用 pair 堆来存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1.5e5 + 9;

int n, m, idx = 1;
int e[N], ne[N], h[N], edge[N], dist[N];
bool st[N];
priority_queue<PII, vector<PII>, greater<PII>> heap; 

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    heap.push({0, 1});
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        
        int distance = t.first, ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; i; i = ne[i])
        {
            int j = e[i];
            if (!st[j])
            {
                dist[j] = min(dist[j], distance + edge[i]);
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    
    memset(edge, 0x3f, sizeof edge);
    
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << dijkstra();
}

Bellman-Ford

有边数限制的最短路

题干

给定一个 个点 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 号点到 号点的最多经过 条边的最短距离，如果无法从 号点走到 号点，输出 impossible。

注意：图中可能 存在负权回路。

输入格式

第一行包含三个整数 , , 。

接下来 行，每行包含三个整数 ，表示存在一条从点 到点 的有向边，边长为 。

点的编号为 。

输出格式

输出一个整数，表示从 号点到 号点的最多经过 条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。

数据范围




任意边长的绝对值不超过 。

输入样例

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

输出样例

1
3

思路分析

本题考查 Bellman-Ford 算法在有边数限制的最短路问题中的应用。Bellman-Ford 算法适用于存在负权边的图，并且可以检测负权回路。对于本题，我们需要在最多经过 条边的限制下求解最短路径。

Bellman-Ford 算法的基本实现：不断进行松弛操作

1
2
3
for n 次
    for 所有a -> b 长为w的边:
        dist[b] = min(dist[b], dist[a] + w)

Bellman-Ford 算法检测负权回路原理：理论上每进行一次松弛操作，就能确定一个点的最短路径，因此进行 n-1 次松弛操作后，理论上会确定所有点的最短路径；如果再进行一次松弛操作，发现仍然有点的距离被更新，说明这条路径上至少有 n 条边、n+1 个点，根据抽屉原理，必然存在一个点被重复访问，说明存在负权回路。

注意：如果要求不超过 k 条边的最短路，则需要进行 k 次松弛操作；这 k 次松弛操作可能会出现“串联”的情况，类似于 DP 时状态转移，本来应该使用上一轮的情况却使用了该轮，因此要用一个临时数组来存储每次松弛操作后的结果，避免“串联”现象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;

int n, m, k;
int dist[N], backup[N];
struct Edge
{
    int st;
    int ed;
    int len;
}edge[N];

void bellmanford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    while (k--)
    {
        memcpy(backup, dist, sizeof dist);
        for (int i = 1; i <= m; i++)
        {
            int st = edge[i].st, ed = edge[i].ed, len = edge[i].len;
            dist[ed] = min(dist[ed], backup[st] + len);
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2)
        cout << "impossible" << '\n';
    else cout << dist[n] << '\n';
    return;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;

    for (int i = 1; i <= m; i++)
        cin >> edge[i].st >> edge[i].ed >> edge[i].len;
    bellmanford();
}

SPFA

SPFA 求最短路

题干

给定一个 个点 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 号点到 号点的最短距离，如果无法从 号点走到 号点，输出 impossible。

输入格式

第一行包含两个整数 和 。
接下来 行每行包含三个整数 ，表示存在一条从点 到点 的有向边，边长为 。

输出格式

输出一个整数，表示从 号点到 号点的最短距离。如果不存在满足条件的路径，则输出 impossible。

数据范围


图中涉及边长绝对值均不超过 。

输入样例

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

输出样例

1
2

思路分析

本题考查 SPFA 算法在有负权边图中的应用。SPFA（Shortest Path Faster Algorithm）是一种基于队列优化的 Bellman-Ford 算法，适用于求解单源最短路径问题，尤其在稀疏图中表现良好。具体步骤如下：

  1. 使用邻接表存储图的边，同时维护一个距离数组 dist[]，初始化为无穷大，起点距离设为 。
  2. 使用一个队列来存储待处理的节点，并使用一个布尔数组 st[] 来标记节点是否在队列中。
  3. 将起点入队，并标记为在队列中。
  4. 当队列不为空时，取出队首节点，遍历其所有邻接边，进行松弛操作，如果距离被更新且邻接点不在队列中，则将邻接点入队并标记。
  5. 重复步骤 4，直到队列为空。
  6. 最终 dist[n] 即为从 1 号点到 n 号点的最短距离，如果为无穷大，则输出 impossible。

注意：本题代码放到 Dijkstra求最短路II 中也可以 AC 并且更快；但是 SPFA 最快情况是 ，最坏情况是 ，因此很多出题人会故意用 的测试数据来卡 SPFA，此时要用 Dijkstra。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int h[N], e[N], ne[N], edge[N], idx = 1;
int n, m;
int dist[N];

int que[N], hh = 1, tt = 0;
bool st[N];

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

void spfa(int u)
{
    memset(dist, 0x3f3f3f3f, sizeof dist);
    dist[u] = 0;
    que[++tt] = u;
    st[u] = true;
    while (hh <= tt)
    {
        int t = que[hh++];
        st[t] = false;  // 出队时马上标记为不在队列中
        for (int i = h[t]; i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + edge[i])
            {
                dist[j] = dist[t] + edge[i];
                if (!st[j])
                {
                    que[++tt] = j;
                    st[j] = true;
                }
            }
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2)
        cout << "impossible";
    else
        cout << dist[n];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    spfa(1);
    return 0;
}

SPFA 判断负环

题干

给定一个 个点 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式

第一行包含整数 和 。

接下来 行每行包含三个整数 ，表示存在一条从点 到点 的有向边，边长为 。

输出格式

如果图中 存在 负权回路，则输出 Yes，否则输出 No。

数据范围

,
,
图中涉及边长绝对值均不超过 。

输入样例

1
2
3
4
3 3
1 2 -1
2 3 4
3 1 -4

输出样例

1
Yes

思路分析

本题考查 SPFA 算法在检测负权回路中的应用。与 Bellman-Ford 算法类似，SPFA 算法可以通过记录每个节点被松弛的次数来检测负权回路。如果某个节点的松弛次数超过 （节点总数），则说明存在负权回路。那我们应该如何知道 n 次操作后仍然有节点的距离被更新？我们可以建立一个数组 cnt[]，每次由于距离更小被更新时，对被更新的节点 cnt[] 加 1，如果 cnt[] 超过 n，则说明存在负权回路。

注意：与上一段代码不同，如果我们只是将节点 1 入队，只能检测从节点 1 出发能否到达的负权回路，而无法检测整个图中的负权回路。因此，我们需要将所有节点都入队，确保能够检测到图中所有可能的负权回路。同时我们不能用数组模拟队列，因为一个节点可能被多次加入队列，如果入队次数超过数组上限就会出错；而如果数组开太大又会 MLE。因此这里使用 STL 的 queue 来实现队列功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 10010;

int h[N], e[M], ne[M], edge[M], idx = 1;
int n, m;
int dist[N], cnt[N];

queue<int> q;
bool st[N];

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

bool spfa()
{
    for (int i = 1; i <= n; i++)
    {
        q.push(i);
        st[i] = true;
    }
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i; i = ne[i])
        {
            int j = e[i];
            
            if (dist[j] > dist[t] + edge[i])
            {
                dist[j] = dist[t] + edge[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()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if (spfa())
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';
    return 0;
}

Floyd

Floyd 求最短路

题干

给定一个 个点 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 个询问，每个询问包含两个整数 和 ，表示查询从点 到点 的最短距离，如果路径不存在，则输出 impossible。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 。

接下来 行，每行包含三个整数 ，表示存在一条从点 到点 的有向边，边长为 。

接下来 行，每行包含两个整数 ，表示询问点 到点 的最短距离。

输出格式

共 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围

,
,
,
图中涉及边长绝对值均不超过 10000。

输入样例

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

输出样例

1
2
impossible
1

思路分析

Floyd 算法适用于求解多源最短路径问题，尤其在图中节点数量较少且需要频繁查询任意两点间最短路径时表现良好。Floyd 算法基于动态规划思想，不妨设 表示经过节点 到节点 作为中间节点时，从节点 到节点 的最短路径长度。

如果经过了节点 ，则路径可以分为两段：从节点 到节点 ，以及从节点 到节点 ，即 。

如果不经过节点 ，则路径长度为 。

因此，状态转移方程为：

第一维可以被省略，即

因此代码模板：

1
2
3
4
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

注意：开始时要把距离初始化为大数，并且将边的距离初始化为边权值，同时将 dist[i][i] 初始化为 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int N = 210;

int n, m;
int dist[N][N];

void floyd()
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int k;
    cin >> n >> m >> k;

    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= n; i++)
        dist[i][i] = 0;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], c);
    }
    floyd();
    while (k--)
    {
        int a, b;
        cin >> a >> b;
        if (dist[a][b] > 0x3f3f3f3f / 2)
            cout << "impossible" << '\n';
        else
            cout << dist[a][b] << '\n';
    }
}

最小生成树

image-20251206113559586

Prim

Prim 算法求最小生成树

题干

给定一个 个点 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 ，其中 表示图中点的集合， 表示图中边的集合，，。

由 中的全部 个顶点和 中 条边构成的无向连通子图被称为 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 的最小生成树。

输入格式

第一行包含两个整数 和 。

接下来 行，每行包含三个整数 ，表示点 和点 之间存在一条权值为 的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围

,
,
图中涉及边的边权的绝对值均不超过 。

输入样例

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

输出样例

1
6

思路分析

Prim 算法适用于求解稠密无向图的最小生成树问题。它与 Dijkstra 算法类似，都是通过贪心策略逐步扩展已知的最小生成树节点集合。具体步骤如下：

  1. 使用邻接矩阵存储图的边，同时维护一个距离数组 dist[]，初始化为无穷大，起点距离设为 。dist[i] 表示点 i 到当前最小生成树已经确定的点的最短距离。
  2. 使用一个布尔数组 st[] 来标记节点是否已被包含在最小生成树中。
  3. 每次从未包含在最小生成树中的节点中选出距离最小的节点，加入最小生成树（先加入再更新，防止自环），并更新其邻接节点的距离。
  4. 重复步骤 3，直到所有节点都被包含在最小生成树中或无法继续扩展。
  5. 最终如果所有节点都被包含在最小生成树中，则输出距离之和；否则输出 impossible。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
const int N = 510;

int n, m;
int dist[N], edge[N][N];
bool st[N];

int prim()
{
    int res = 0;
    memset(dist, 0x3f, sizeof dist);
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        // 选出未加入最小生成树的点中距离最小的点

        st[t] = true;
        // 将该点加入最小生成树

        if (!i)
            dist[t] = 0;
        // 如果是第一个点，则将距离设为0

        if (i && dist[t] > 0x3f3f3f3f / 2)
            return dist[t];
        // 如果不是第一个点且距离为大数，说明不是连通图，不存在最小生成树

        res += dist[t];
        // 将该点的距离加入结果

        for (int j = 1; j <= n; j++)
        {
            if (!st[j])
                dist[j] = min(dist[j], edge[t][j]);
        }
        // 用该点更新其他点的距离
    }
    return res;
}

int main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    memset(edge, 0x3f, sizeof edge);
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edge[a][b] = edge[b][a] = min(edge[a][b], c);
    }
    int u = prim();
    if (u > 0x3f3f3f3f / 2)
        cout << "impossible" << '\n';
    else
        cout << u;
}

Kruskal 算法

Kruskal 算法求最小生成树

题干

给定一个 个点 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 ，其中 表示图中点的集合， 表示图中边的集合，，。

由 中的全部 个顶点和 中 条边构成的无向连通子图被称为 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 的最小生成树。

输入格式

第一行包含两个整数 和 。

接下来 行，每行包含三个整数 ，表示点 和点 之间存在一条权值为 的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围

,
,
图中涉及边的边权的绝对值均不超过 。

输入样例

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

输出样例

1
6

思路分析

Kruskal 算法适用于稀疏图的最小生成树问题。

它的步骤为：

  1. 将所有边按权重从小到大排序。

  2. 依次选择边，若选择的边不会形成环，则将其加入最小生成树中，直到包含所有顶点或边用尽。

排序的时间复杂度为 ，而将边加入最小生成树的过程可以通过并查集实现，时间复杂度接近 ，因此整体时间复杂度为 。由于 Kruskal 算法只需要遍历边即可，因此可以直接用结构体存边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n, m;
int p[N];

struct Edge
{
    int st;
    int ed;
    int len;
    bool operator<(const Edge &w) const
    {
        return len < w.len;
    }
} edge[N];

int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
// 并查集的查找函数，查找一个节点的祖宗节点

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> edge[i].st >> edge[i].ed >> edge[i].len;
    for (int i = 1; i <= n; i++)
        p[i] = i;
    sort(edge + 1, edge + 1 + m);
    int cnt = 0, res = 0;
    // cnt记录已经加入最小生成树的边数
    // res记录最小生成树的边权和
    for (int i = 1; i <= m; i++)
    {
        int st = edge[i].st, ed = edge[i].ed, len = edge[i].len;
        st = find(st), ed = find(ed);
        if (st != ed)
        {
            res += len;
            cnt++;
            p[st] = ed;
        }
        // 如果两个节点不在同一个集合中，则将它们合并
    }
    if (cnt < n - 1)
        cout << "impossible" << '\n';
    else
        cout << res;
}

二分图

定义：二分图，又称二部图，是一类结构特殊的图。它的顶点集可以划分为两个互不相交的子集，使得图中的每条边都连接这两个集合之间的一对点，而不会连接同一集合内部的点。

二分图也可以由下列性质等价地定义：

  • 图 是可 2‑着色的。也就是说，可以用至多两种颜色给图的所有顶点染色，并且保证相邻顶点颜色不同。
  • 图 中不存在奇数长度的环。

image-20251206113708695

染色法

染色法判定二分图

题干

给定一个 个点 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式

第一行包含两个整数 和 。

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

输出格式

如果给定图是二分图，则输出 Yes，否则输出 No。

数据范围

输入样例

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

输出样例

1
Yes

思路分析

由二分图的等价定义 图是可 2‑着色的 可知，只要给每个点染色，最后没有矛盾就是二分图，有矛盾就不是。

宽度优先遍历

  1. 遍历所有节点，如果节点未染色，则从该节点开始进行宽度优先搜索染色（可能不是一个连通图，因此要遍历所有节点）
  2. 对于 bfs 函数，先将起始节点染成颜色 1，并将其加入队列
  3. bfs 时，取出队首及其颜色，将相邻节点染成相反颜色，如果发现相邻节点颜色与当前节点相同，则说明不是二分图
  4. 如果所有节点都能成功染色，则说明图是二分图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 2e5 + 10;

int n, m;
int h[N], e[M], ne[M], idx = 1;
int st[N];
// st数组存颜色，0代表未染色，1代表颜色1，2代表颜色2
// 3 - color表示另一种颜色
queue<PII> q;

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

bool bfs(int u)
{
    st[u] = 1;
    q.push({u, st[u]});
    while (!q.empty())
    {
        PII t = q.front();
        q.pop();
        int point = t.first, color = t.second;
        for (int i = h[point]; i; i = ne[i])
        {
            int j = e[i];
            if (!st[j])
            {
                st[j] = 3 - color;
                q.push({j, st[j]});
            }
            else if (st[j] == color)
                return false;
            // 如果j点没染色，就染成相反颜色
            // 如果j点已经染色且颜色与当前点相同，则说明不是二分图
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!st[i])
            if (!bfs(i))
            {
                cout << "No" << '\n';
                return 0;
            }
    }
    cout << "Yes" << '\n';
    return 0;
}

深度优先遍历

  1. 遍历所有节点，如果节点未染色，则从该节点开始进行深度优先搜索染色（可能不是一个连通图，因此要遍历所有节点）
  2. 对于 dfs 函数，传入两个参数：当前节点和要染成的颜色
  3. 先将当前节点染成指定颜色，然后递归染色相邻节点，如果相邻节点颜色与当前节点相同，则说明不是二分图；如果相邻节点未染色，则将对该节点和相反颜色进行 dfs
  4. 如果最后所有节点都能成功染色，则说明图是二分图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 2e5 + 10;

int n, m;
int h[N], e[M], ne[M], idx = 1;
int st[N];
queue<PII> q;

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

bool dfs(int u, int color)
{
    st[u] = color;
    // 将当前节点染成指定颜色
    for (int i = h[u]; i; i = ne[i])
    {
        int j = e[i];
        if (st[j] == color)
            return false;
        // 如果相邻节点颜色与当前节点相同，则说明不是二分图
        else if (!st[j])
            if (!dfs(j, 3 - color))
                return false;
        // 如果相邻节点未染色，则将对该节点和相反颜色进行dfs
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!st[i])
            if (!dfs(i, 1))
            {
                cout << "No" << '\n';
                return 0;
            }
    }
    cout << "Yes" << '\n';
    return 0;
}

匈牙利算法

二分图的最大匹配

题干

给定一个二分图，其中左半部包含 个点（编号 1∼ ），右半部包含 个点（编号 1∼ ），二分图共包含 条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

二分图的匹配：给定一个二分图 ，在 的一个子图 中， 的边集 中的任意两条边都不依附于同一个顶点，则称 是一个匹配。

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

输入格式

第一行包含三个整数 、 和 。

接下来 行，每行包含两个整数 和 ，表示左半部点集中的点 和右半部点集中的点 之间存在一条边。

输出格式

输出一个整数，表示二分图的最大匹配数。

数据范围

,
,
,

输入样例

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

输出样例

1
2

思路分析

求二分图的最大匹配可以用匈牙利算法解决。匈牙利算法的具体步骤类似于找男生女生配对的过程：
以这组数据为例：

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

对于男 1，他有两个选择，女 1 或女 2；此时先让他选择女 1，也就是让男 1 与女 1 配对；接着遍历男 2，此时他只有女 1 一个选择，但女 1 已经被男 1 占用了，这时候就要看男 1 能否换个人：如果男 1 可以换一个没对象的人（女 2），把男 1 换到女 2，然后再将男 2 与女 1 配对；如果男 1 不能换人（比如女 2 已经有对象了），那就说明男 2 没法配对成功。

对于这个匹配的过程，我们可以用一个 match[] 数组来表示右半部点集中的每个点当前匹配的左半部点集中的点，如果没有匹配则为 0；对于每一个男生，我们可以写一个 find 函数来找到他能否配对成功，如果能的话就更新 match[] 数组，同时返回 true，否则返回 false；并且我们可以递归调用 find 函数实现“换对象”的过程。

注意：为了方便遍历每一个男生可以配对的女生，虽然是稠密图，但我们仍然使用邻接表存储图的边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 510, M = 1e5 + 10;

int n1, n2, m;
int h[N], e[M], ne[M], idx = 1;
// 邻接表存的值只有女生
bool st[N];
// st数组用来标记每一轮女生是否被访问过
// 它的意义是防止同一轮换对象时，同一个女生一直被重复访问，导致死循环
int match[N];
// match数组用来存每个女生当前匹配的男生

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; i = ne[i])
	{
		int j = e[i];
        // 遍历男生x能配对的女生j
		if (!st[j])
		{
			st[j] = true;
            // 如果女生j该轮还没被访问过，则标记为已访问
			if (!match[j] || find(match[j]))
			{
				match[j] = x;
				return true;
                // 如果女生j没有对象，或者她的对象能换人成功
                // 则将女生j与男生x配对成功，返回true
			}
		}
	}	
	return false;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n1 >> n2 >> m;
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
        // 虽然是无向图，但由于我们只访问男生，因此只需要存男生到女生的边
    }
    int res = 0;
    for (int i = 1; i <= n1; i++)
    {
        memset(st, 0, sizeof st);
        // 由于st表示每一轮的女生状态，下一轮时需要将st数组清空，参考上述例子，如果不清空的话，男2就无法访问女1
        if (find(i))
            res++;
    }
    cout << res << '\n';
}