No.30 · 拓扑排序序列

点击展开题目

给定一个包含 $n$ 个顶点的有向无环图（DAG），顶点编号为从 $0$ 到 $n-1$。图的邻接矩阵 $G$ 中，$G[i][j]=1$ 表示存在一条从顶点 $i$ 指向顶点 $j$ 的有向边，$G[i][j]=0$ 表示不存在这样的边。你需要返回该图的拓扑排序序列。

拓扑排序是指将图中所有顶点排成一个线性序列，使得对于图中的每一条有向边 $(u, v)$，$u$ 在序列中总是位于 $v$ 的前面。

注：每次有多个顶点可以选择时，总是选择编号最小的那个。

输入描述

• 邻接矩阵 $G$（二维数组形式给出），表示有向无环图；
• 整数 $n$，表示图中顶点的数量（顶点编号为 $0$ 到 $n-1$）；
• 整型指针 returnSize，返回前需将 *returnSize 修改为拓扑序列的长度。

输出描述

• 返回存储拓扑排序序列的一维数组指针。

样例 1

输入

G = [[0,1,1,1],[0,0,1,0],[0,0,0,0],[0,0,1,0]]

输出

[0,1,3,2]

解释

对应的有向无环图结构如下：

        1
      /   \
     v     v
0 --------> 2
     \     ^
      v   /
        3

图中包含的有向边为：$0 \to 1$、$0 \to 2$、$0 \to 3$、$1 \to 2$、$3 \to 2$。 该图合法的拓扑排序序列包括 [0, 1, 3, 2] 和 [0, 3, 1, 2]。根据题目要求，当存在多个入度为 $0$ 的候选顶点时总是优先选择编号最小的顶点，因此唯一确定的拓扑排序序列为 0 1 3 2（即 [0, 1, 3, 2]）。

---

思路

本题在标准拓扑排序（Kahn 算法）的基础上增加了一个约束：当同时存在多个入度为 $0$ 的可选顶点时，总是优先选择编号最小的顶点——这等价于求解有向无环图的字典序最小拓扑排序序列。

核心思路：Kahn 算法 + 小根堆（最小优先队列）

在普通 Kahn 算法中，我们使用普通队列（queue）维护所有当前入度为 $0$ 的顶点，因为普通拓扑排序对同批无前驱顶点的先后顺序没有要求。而在本题中，为了保证每次从候选集合中取出的都是编号最小的顶点，只需将普通队列替换为小根堆（最小优先队列 priority_queue<int, vector<int>, greater<int>>）：

• 任意时刻，堆中存放的都是当前所有前置依赖已全部解除（即 inDegree == 0）的顶点；
• 堆顶元素 q.top() 必然是当前所有可排入序列的顶点中编号最小的一个。

算法步骤

1. 统计各顶点初始入度： 创建长度为 $n$ 的入度数组 inDegree 并初始化为 $0$。通过两层循环遍历邻接矩阵 $G$ 的所有元素 $G[i][j]$：若 $G[i][j] = 1$，说明存在一条从顶点 $i$ 指向顶点 $j$ 的有向边，将顶点 $j$ 的入度加一（inDegree[j]++）。
2. 小根堆初始化： 遍历所有顶点 $i \in [0, n-1]$，将所有初始入度为 $0$（inDegree[i] == 0）的顶点压入小根堆 q 中。
3. 贪心取最小顶点并更新后继入度： 动态分配长度为 $n$ 的结果数组 result，用下标 k 记录已排入拓扑序列的顶点数。当小根堆 q 非空时循环执行：
   • 取出并弹出堆顶元素 u（当前入度为 $0$ 且编号最小的顶点），将其写入结果序列 result[k++] = u；
   • 遍历邻接矩阵的第 $u$ 行（$v = 0 \dots n-1$）：若 $G[u][v] = 1$，说明存在有向边 $u \to v$，将邻接点 $v$ 的入度减一（inDegree[v]--）；
   • 若减一后 inDegree[v] == 0，说明顶点 $v$ 的所有前置依赖均已排入序列，立即将 $v$ 压入小根堆 q 中等待后续选择。
4. 返回结果： 题目保证输入为有向无环图（DAG），循环结束时全部 $n$ 个顶点均已按字典序最小拓扑序排入 result。将 *returnSize 赋值为 k（即 $n$），返回 result 即可。

复杂度分析

• 时间复杂度：$O(n^2)$（精确分析为 $O(n^2 + n \log n)$，若按宽泛上界估计记作 $O(n^2 \log n)$）。统计初始入度需扫描 $n \times n$ 邻接矩阵，耗时 $O(n^2)$；在拓扑排序主循环中，每个顶点恰好入堆、出堆各一次（共 $n$ 次，每次堆操作耗时 $O(\log n)$，合计 $O(n \log n)$），且每个顶点出堆时需扫描邻接矩阵的一整行（共 $n$ 次扫描、每次 $O(n)$，合计 $O(n^2)$）。
• 空间复杂度：$O(n)$。主要开销为长度为 $n$ 的入度表 inDegree、最多同时容纳 $n$ 个顶点的小根堆 q 以及长度为 $n$ 的结果序列 result。

---

C++

/**
 * @param G: 邻接矩阵，表示有向无环图，按二维数组的方式用下标即可访问内部元素
 * @param n: 图中顶点的数量
 * @param returnSize: 用于返回拓扑排序序列的长度
 * @return: 返回拓扑序列的数组指针
 * 注意：返回前请修改 *returnSize 为数组长度
 */
int* topologicalSort(int** G, int n, int* returnSize) {
    priority_queue<int, vector<int>, greater<int>> q;
    vector<int> inDegree(n, 0);

    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            if(G[i][j]){
                inDegree[j] ++;
            }
        }
    }

    for(int i = 0; i < n; i ++){
        if(inDegree[i] == 0){
            q.push(i);
        }
    }

    int* result = new int[n];
    int k = 0;
    while(q.size()){
        int u = q.top();
        q.pop();
        result[k ++] = u;
        for(int v = 0; v  < n; v ++){
            if(G[u][v]){
                inDegree[v] --;
                if(inDegree[v] == 0){
                    q.push(v);
                }
            }
        }
    }
    *returnSize = k;
    return result;
}

相似题目

• AtCoder ABC223 D - Restricted Permutation — 与本题完全同构的经典题：利用 Kahn 算法结合小根堆（优先队列）求字典序最小的拓扑排序序列。
• 210. 课程表 II — 拓扑排序构造合法线性序列的标准模板题。
• 2115. 从给定原材料中找到所有可以做出的菜 — 基于入度统计与队列推进的拓扑排序应用题。
• 1203. 项目管理 — 双层拓扑排序（组间拓扑序 + 组内拓扑序）构造满足多重依赖关系的序列。
• 269. 火星词典 — 从词典序约束建有向图并求合法的拓扑排序序列。

---

No.29 · 有向无环图的判定

点击展开题目

给定一个由邻接矩阵表示的有向图，判断该图是否是有向无环图（DAG）。有向无环图是指不存在任何环的有向图，即无法从某个顶点出发经过若干条边后再次回到该顶点。

输入描述

• 邻接矩阵 $G$（二维数组形式给出），表示有向图，其中 $G[i][j] \ne 0$（本题中为 $1$）表示存在从顶点 $i$ 指向顶点 $j$ 的有向边；
• 整数 $n$，表示图中顶点的数量（顶点编号为从 $0$ 到 $n-1$）。

输出描述

• 返回一个布尔值：true 表示该图是有向无环图（DAG），false 表示图中存在有向环。

样例 1

输入

G = [[0,1,1,1],[0,0,1,0],[0,0,0,0],[0,0,1,0]]

输出

true

解释

邻接矩阵对应的有向图结构如下：

        1
      /   \
     v     v
0 --------> 2
     \     ^
      v   /
        3

图中包含的有向边为：$0 \to 1$、$0 \to 2$、$0 \to 3$、$1 \to 2$、$3 \to 2$。 该图不存在任何环（存在合法的拓扑序列如 $0, 1, 3, 2$），因此返回 true。

样例 2

输入

G = [[0,1,0,1],[0,0,1,0],[1,0,0,0],[0,0,1,0]]

输出

false

解释

邻接矩阵对应的有向图结构如下：

        1
      /   \
     v     v
    0 <---- 2
     \     ^
      v   /
        3

图中包含的有向边为：$0 \to 1$、$0 \to 3$、$1 \to 2$、$2 \to 0$、$3 \to 2$。 存在有向环 $0 \rightarrow 1 \rightarrow 2 \rightarrow 0$（以及 $0 \rightarrow 3 \rightarrow 2 \rightarrow 0$），因此返回 false。

---

思路

判定一个有向图是否为有向无环图（DAG, Directed Acyclic Graph），主要有两种经典思路：

• 方法一（BFS / Kahn 拓扑排序）：不断剥离入度为 $0$ 的顶点，检验最终能否消去全部 $n$ 个顶点；
• 方法二（DFS 三色标记法）：在深度优先搜索过程中维护顶点的访问状态，检验是否存在指向「当前递归调用栈中祖先顶点」的回边（Back Edge）。

---

方法一：拓扑排序（BFS / Kahn 算法）

核心性质：DAG 与拓扑排序的等价性 在图论中，有向图能否完成拓扑排序与其是否无环具有充要等价关系：

1. 若图是 DAG：图中必然至少存在一个入度为 $0$ 的顶点（不依赖任何前置顶点）。将该顶点及其发出的所有有向边从图中删去后，剩余的子图依然是 DAG，可以继续剥离出新的入度为 $0$ 的顶点，直到图中全部 $n$ 个顶点均被依次剥离。
2. 若图中存在有向环：环上的任意顶点都至少有一条来自环上前驱顶点的入边，导致环上所有顶点的入度恒 $\ge 1$。在剥离过程中，环上顶点以及依赖该环的后续顶点永远无法将入度削减至 $0$，从而无法入队。最终成功出队的顶点总数 cnt 必然严格小于总顶点数 $n$。

算法步骤

1. 统计各顶点初始入度：
   • 开辟长度为 $n$ 的入度数组 inDegree，初始值全为 $0$；
   • 双重循环遍历邻接矩阵 $G$：若 $G[i][j]$ 非零（存在有向边 $i \to j$），则将终点 $j$ 的入度加一（inDegree[j]++）。
2. 零入度顶点入队：
   • 建立辅助队列 q，遍历所有顶点 $i \in [0, n-1]$；
   • 将所有初始入度为 $0$（inDegree[i] == 0）的顶点压入队列 q，作为拓扑排序的起始层。
3. 广度优先拓扑消去：
   • 维护已拓扑输出的顶点计数器 cnt = 0；
   • 当队列 q 非空时，弹出队首顶点 $u$，并将计数器 cnt 加一；
   • 枚举顶点 $u$ 的所有出边邻居 $v \in [0, n-1]$：若存在有向边 $u \to v$（G[u][v] 非零），则模拟删去该边，将顶点 $v$ 的入度减一（inDegree[v]--）；
   • 若减一后顶点 $v$ 的入度恰好变为 $0$（说明指向 $v$ 的所有前置顶点均已处理完毕），则将 $v$ 压入队列 q。
4. 判环与返回：
   • 当队列排空后，判断已处理的顶点数 cnt 是否等于图的总顶点数 $n$；
   • 若 cnt == n，说明全部顶点均成功拓扑消去，图中无环，返回 true；否则说明剩余 n - cnt 个顶点因陷入环路依赖而无法入队，返回 false。

---

方法二：深度优先搜索（DFS 三色标记法）

核心思想：回边（Back Edge）检测 在无向图中，只需一个布尔数组 visited 即可判环；但在有向图中，访问到一个已经访问过的顶点并不一定意味着有环（例如两条不同路径汇合到同一个已搜索完毕的分支顶点，属于横叉边或前向边，不构成环）。只有当搜索过程中遇到一条指向当前 DFS 递归路径上的祖先顶点的边（即回边）时，才真正构成了有向环。

为此，我们用三状态数组 state（对应经典的三色标记法）区分顶点的生命周期：

• UNVISITED (0)（白色）：该顶点尚未被访问；
• VISITING (1)（灰色）：该顶点正在被当前 DFS 路径递归访问中（即位于当前递归调用栈上，其后代子图尚未搜索完毕）；
• FINISHED (2)（黑色）：该顶点及其所有可达后代均已搜索完毕，且确认从该顶点出发的子图中不存在任何环（安全顶点）。

算法步骤

1. 初始化状态：开辟长度为 $n$ 的数组 state，初始值全为 UNVISITED (0)。
2. 外层遍历各连通分支：由于有向图不一定强连通，外层循环依次检查每个顶点 $i \in [0, n-1]$。若 state[i] == UNVISITED，则以 $i$ 为起点调用 DFS(G, n, i, state) 检测是否存在有向环。
3. 递归搜索与状态转移（DFS 函数，返回 true 表示发现环）：
   • 入栈染灰：刚进入顶点 $u$ 时，将其状态设为 state[u] = VISITING，标记 $u$ 已加入当前递归路径；
   • 枚举出边邻居：遍历所有顶点 $v \in [0, n-1]$，若 !G[u][v]（无有向边 $u \to v$）则直接跳过；
   • 按邻居 $v$ 的状态分类讨论：
     • 若 state[v] == UNVISITED：递归调用 DFS(G, n, v, state)。若下层递归返回 true（后代中发现环），则立即向上层传递返回 true；
     • 若 state[v] == VISITING：说明从当前路径上的顶点 $u$ 指向了仍在当前递归栈中的祖先顶点 $v$，即捕获到一条回边 $v \leadsto u \to v$，图中必然存在有向环，立即返回 true；
     • 若 state[v] == FINISHED：说明顶点 $v$ 及其后续子图此前已被彻底检查过且无环，直接跳过即可（避免重复搜索）。
   • 出栈染黑：当顶点 $u$ 的所有出边均探测完毕且未发现环时，将其状态更新为 state[u] = FINISHED，并返回 false。
4. 汇总结果：外层循环中，一旦任意一次 DFS 返回 true（发现有环），isDAG 立即返回 false；若所有顶点均顺利完成搜索且未发现环，最终返回 true。

---

复杂度分析

• 时间复杂度：两种方法均为 $O(n^2)$。其中 $n$ 为图中顶点的数量。
  • 方法一（BFS 拓扑排序）：预处理扫描 $n \times n$ 邻接矩阵统计入度耗时 $O(n^2)$；每个顶点最多入队、出队一次，每次出队遍历矩阵的一行（$n$ 个元素）更新入度，累计耗时 $O(n^2)$。
  • 方法二（DFS 三色标记）：得益于 FINISHED 状态的记忆化剪枝，每个顶点最多进入 DFS 递归一次（从 UNVISITED 变为 VISITING 再变为 FINISHED）；在递归函数内部需要遍历邻接矩阵的第 $u$ 行（共 $n$ 列）寻找出边，因此总时间复杂度同样为 $O(n^2)$。
• 空间复杂度：两种方法均为 $O(n)$。
  • 方法一：需要长度为 $n$ 的入度数组 inDegree 和最多容纳 $n$ 个顶点的辅助队列 q。
  • 方法二：需要长度为 $n$ 的状态数组 state，以及最坏情况下（有向图退化为长度为 $n$ 的单链）深度为 $O(n)$ 的递归调用栈空间。

---

C++ (BFS)

/**
 * @param G: 邻接矩阵，表示有向图，按二维数组的方式用下标即可访问内部元素
 * @param n: 图中顶点的数量
 * @return: 返回布尔值，true表示是有向无环图，false表示存在环
 */
bool isDAG(int** G, int n) {
    queue<int> q;
    vector<int> inDegree(n, 0);

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            if(G[i][j])
            {
                inDegree[j] ++;// j的入度加一
            }
        }
    }

    for(int i = 0; i < n; i ++)
    {
        if(inDegree[i] == 0)
        {
            q.push(i);
        }
    }

    int cnt = 0;
    while(q.size())
    {
        int u = q.front();
        q.pop();
        cnt ++;
        for(int v = 0; v < n; v ++)
        {
            if(G[u][v])
            {
                inDegree[v] --;
                if(inDegree[v] == 0)
                {
                    q.push(v);
                }
            }
        }
    }

    return cnt == n;
}

C++ (DFS)

/**
 * @param G: 邻接矩阵，表示有向图，按二维数组的方式用下标即可访问内部元素
 * @param n: 图中顶点的数量
 * @return: 返回布尔值，true表示是有向无环图，false表示存在环
 */
#define UNVISITED 0
#define VISITING 1
#define FINISHED 2

bool DFS(int **G, int n, int u, vector<int>& state)
{
    state[u] = VISITING;
    for(int v = 0; v < n; v ++)
    {
        if(!G[u][v])
        {
            continue;
        }
        if(state[v] == UNVISITED)
        {
            if(DFS(G, n, v, state))
            {
                return true;
            }
        }else if(state[v] == VISITING){
            return true;
        }
    }
    state[u] = FINISHED;
    return false;
}


bool isDAG(int** G, int n) {
    vector<int> state(n, UNVISITED);
    for(int i = 0; i < n; i ++)
    {
        if(state[i] == UNVISITED)
        {
            if(DFS(G, n, i, state))
            {
                return false;
            }
        }
    }
    return true;
}

相似题目

• AcWing 848. 有向图的拓扑序列 — Kahn 算法（BFS 维护入度）求有向图拓扑排序并判定是否有环的标准模板题。
• 207. 课程表 — 本题的力扣对标原题，判断有向图课程先修关系是否存在环（即是否为 DAG）。
• 210. 课程表 II — 在判定有向无环图的基础上，构造并输出任意一个合法的拓扑排序序列。
• 802. 找到最终的安全状态 — 反向建图结合拓扑排序，识别所有不在环上且不会进入环的安全节点。
• 1462. 课程表 IV — 有向无环图上的拓扑排序与先修可达性传递闭包判定。
• 1857. 有向图中最大颜色值 — 拓扑排序判环 + DAG 动态规划进阶题。

---

No.28 · 无权图最短路径

点击展开题目

给定一个有向图的邻接表 $G$，该图共有 $n$ 个顶点（编号为从 $0$ 到 $n-1$）和 $m$ 条边，且所有边权均为 $1$。请你计算从顶点 $0$ 出发到达图中所有其他顶点的最短距离，并将结果存储在一个数组中。如果某个顶点不可达，则对应位置记为 $-1$。

输入描述

• 邻接表 $G$（二维数组形式给出），表示有向图；
• 整数 $n$（$1\le n\le 500$），表示图中顶点的数量；
• 数组 $colSize$（一维数组），$colSize[i]$ 表示顶点 $i$ 的出边数量（即邻居列表长度）；
• 结果数组 $d$（一维数组），预先分配大小为 $n$。

输出描述

• 将计算出的最短距离直接写入结果数组 $d$ 中。对于无法到达的顶点，对应的值设置为 $-1$。

样例 1

输入

n = 5
G = [[1,2],[],[3],[],[]]

输出

[0,1,1,2,-1]

解释

邻接表表示的有向图结构如下：

       0
     /   \
    v     v
    1      2
           |
           v
           3        4 (孤立顶点，入度与出度均为0)

从顶点 $0$ 出发到达各顶点的最短路径：

• $0 \to 0$：起始顶点，距离为 $0$；
• $0 \to 1$：存在边 $0 \to 1$，距离为 $1$；
• $0 \to 2$：存在边 $0 \to 2$，距离为 $1$；
• $0 \to 3$：最短路径为 $0 \to 2 \to 3$，距离为 $2$；
• $0 \to 4$：不存在到达顶点 $4$ 的有向路径，距离为 $-1$。

最终距离数组为 [0, 1, 1, 2, -1]。

---

---

思路

对于所有边权均为 $1$（或等权非负）的单源最短路径问题，不需要使用复杂度较高的 Dijkstra 或 Bellman-Ford 算法，直接使用广度优先搜索（BFS）即可在线性时间内求解。

核心性质：BFS 的步数最优性

在无权图（或所有边权均为 $1$ 的图）中，BFS 具备以下核心性质：

1. 两段性与单调性：队列中保存的顶点按照与起点的距离升序排列，队列内任意时刻顶点的距离差最多为 $1$。
2. 首次访问即最优：从队列中第一次扩展并访问到某个顶点 $v$ 时，此时记录的距离 $d[v] = d[u] + 1$ 必然是从起点到该顶点的全局最短路径长度。后续任何路径到达 $v$ 的步数必然 $\ge d[v]$。

算法步骤

1. 初始化：
   • 将距离数组 $d$ 中的所有顶点值初始化为 $-1$，用来同时表示「尚未访问」与「不可达」；
   • 将起点 $0$ 的距离设为 $d[0] = 0$，表示起点到自身距离为 $0$；
   • 建立辅助队列 $q$，将起点 $0$ 入队。
2. 广度优先逐层扩展：
   • 当队列不为空时，取出队首顶点 $u$ 并出队；
   • 遍历顶点 $u$ 的邻接链表中的所有出边邻居 $v = G[u][j]$（共 $colSize[u]$ 个）；
   • 若 $d[v] == -1$（说明邻居 $v$ 此前从未被访问过）：
     • 更新最短距离：$d[v] = d[u] + 1$；
     • 将邻居顶点 $v$ 压入队列 $q$。
3. 结束与返回：
   • 队列排空后，所有从起点 $0$ 可达的顶点均已得到最短距离；
   • 仍为 $-1$ 的位置即为不可达顶点，结果直接保存在数组 $d$ 中。

复杂度分析

• 时间复杂度：$O(n + m)$。其中 $n$ 为顶点数，$m$ 为边数。图使用邻接表存储，每个顶点最多入队、出队一次（$O(n)$），每条有向边最多被遍历一次（$O(m)$），总体达到线性最优时间复杂度。
• 空间复杂度：$O(n)$。需要一个辅助队列 $q$（最多容纳 $n$ 个顶点）和长度为 $n$ 的距离数组 $d$。

---

---

C++

void shortestPaths(int** G, int n, int *colSize, int *d) {
    // 初始化所有顶点的距离为 -1，表示尚未访问
    for (int i = 0; i < n; ++i) {
        d[i] = -1;                                         // 标记顶点i为未访问
    }
    // 设置起点0的初始距离
    d[0] = 0;                                              // 起点距离为0
    // 广度优先搜索
    queue<int> q;                                          // 辅助队列
    q.push(0);                                             // 将起点入队
    while (!q.empty()) {
        int u = q.front();                                 // 取出队首节点
        q.pop();                                           // 弹出队首节点
        for (int j = 0; j < colSize[u]; ++j) {
            int v = G[u][j];                               // u的第j个邻居
            if (d[v] == -1) {                              // 若邻居v未访问
                d[v] = d[u] + 1;                           // 更新v的距离
                q.push(v);                                 // 将v入队继续搜索
            }
        }
    }
}

相似题目

• AcWing 847. 图中点的层次 — 本题的标准原型题，求无权图中从 1 号点到 n 号点的最短距离。
• AcWing 1134. 最短路计数 — 无权图 BFS 最短路基础上的路径计数扩展。
• 1091. 二进制矩阵中的最短路径 — 网格图上的八方向无权最短路径 BFS。
• 841. 钥匙和房间 — 有向图连通性遍历与可达性判断。
• 2608. 图中的最短环 — 枚举起点结合 BFS 求解无向图最短环长度。
• 1376. 通知所有员工所需的时间 — 树形图遍历与距离累加。

---

No.27 · 无向图全顶点最短距离

点击展开题目

给定一个包含 $n$ 个顶点（编号从 $0$ 到 $n-1$）的无向图，并用邻接矩阵表示顶点之间的距离。你需要计算从任意起点到任意终点的最短距离。无法到达的顶点的距离为 $-1$。

输入描述

• 整数 $n$（$1\le n\le 500$），表示图中顶点的数量；
• 邻接矩阵 $G$（二维数组形式给出），其中 $G[i][j] \ge 0$ 表示边权，$-1$ 表示顶点 $i$ 与顶点 $j$ 之间没有直接边（不可达），对角线 $G[i][i] = 0$。

输出描述

• 返回一个大小为 $n \times n$ 的二维数组 $d$，其中 $d[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 的最短距离；若两顶点间不可达，则对应位置的值为 $-1$。

样例 1

输入

n = 4
G = [[0,2,-1,4],[2,0,1,-1],[-1,1,0,3],[4,-1,3,0]]

输出

[[0,2,3,4],[2,0,1,4],[3,1,0,3],[4,4,3,0]]

解释： 图由 4 个顶点构成，邻接矩阵与带权边拓扑结构如下：

        0
       / \
   (2)/   \(4)
     /     \
    1       3
     \     /
   (1)\   /(3)
       \ /
        2

各顶点间通过中转节点优化出的最短距离分析如下：

• $0 \to 1$：直接相连，距离为 $2$。
• $0 \to 2$：中转路径 $0 \to 1 \to 2$，距离为 $2 + 1 = 3$（优于其他路线）。
• $0 \to 3$：直接相连，距离为 $4$；若走 $0 \to 1 \to 2 \to 3$，距离为 $2 + 1 + 3 = 6 > 4$，故最短距离为 $4$。
• $1 \to 3$：中转路径 $1 \to 2 \to 3$，距离为 $1 + 3 = 4$。 最终得到的全源最短距离矩阵即为输出所示。

样例 2

输入

n = 3
G = [[0,1,-1],[1,0,-1],[-1,-1,0]]

输出

[[0,1,-1],[1,0,-1],[-1,-1,0]]

解释： 图的拓扑结构与边权如下：

    0 -------- 1       2 (孤立点)
        (1)

顶点 $2$ 与顶点 $0, 1$ 之间均无边相连，无法到达，故对应的最短距离维持 $-1$。

---

---

思路

本题要求计算无向图中任意两点之间的最短距离（全源最短路径问题，All-Pairs Shortest Paths）。由于题目以稠密邻接矩阵形式给出图且需要计算所有顶点对之间的距离，最经典、简洁的解决方案是 Floyd-Warshall 算法。

1. 算法核心原理（动态规划思想）

Floyd 算法本质上是一种基于动态规划的算法：

• 状态定义：设 $d^k[i][j]$ 表示「仅允许使用编号在 $\{0, 1, \dots, k\}$ 以内的顶点作为中间中转节点时，从顶点 $i$ 到顶点 $j$ 的最短距离」。
• 状态转移方程：

  $$d^k[i][j] = \min(d^{k-1}[i][j], \; d^{k-1}[i][k] + d^{k-1}[k][j])$$

  即考虑是否将顶点 $k$ 纳入当前路径的中转点：
  • 如果不经过顶点 $k$，则最短路径维持 $d^{k-1}[i][j]$；
  • 如果经过顶点 $k$，则路径拆分为 $i \to k$ 和 $k \to j$，前提是两段子路径均可达（即 $d[i][k] \ne -1$ 且 $d[k][j] \ne -1$）。
• 空间优化：由于转移仅依赖于第 $k-1$ 阶段，可以直接在二维数组 $d[i][j]$ 上进行原地更新（外层枚举 $k$，内层枚举 $i$ 与 $j$）。

2. 处理细节

• 初始化：先将邻接矩阵 $G$ 原样拷贝至答案矩阵 $d$ 中，$d[i][j] = G[i][j]$。
• 不可达判定：若 $d[i][k] == -1$ 或 $d[k][j] == -1$，说明无法经由中间点 $k$ 进行中转，直接跳过该次松弛。
• 松弛更新条件： 若当前 $d[i][j] == -1$（之前不可达但现在经 $k$ 可达），或者经 $k$ 的中转距离严格小于当前已知距离（$d[i][k] + d[k][j] < d[i][j]$），则更新 $d[i][j] = d[i][k] + d[k][j]$。

3. 复杂度分析

• 时间复杂度：$O(n^3)$。三重嵌套循环，最外层枚举中转节点 $k \in [0, n-1]$，内层两重循环遍历顶点对 $(i, j)$，常数极小。
• 空间复杂度：$O(n^2)$。需要一个 $n \times n$ 的二维矩阵存储并返回全源最短路径距离。

---

---

C++

void getAllPairsShortestPaths(int** G, int n, int** d) {
    // 初始化：将原图距离拷贝到结果矩阵中
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = G[i][j];                      // 直接复制初始距离
        }
    }

    // Floyd 算法：枚举每个顶点作为中介点，更新所有顶点对最短距离
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (d[i][k] == -1 || d[k][j] == -1) continue;    // 若 i->k 或 k->j 不可达，跳过
                if (d[i][j] == -1 || d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];                  // 通过 k 的路径更短则更新
                }
            }
        }
    }
}

相似题目

• AcWing 854. Floyd求最短路 — 经典 Floyd 全源最短路径标准模板题。
• 1334. 阈值距离内邻居最少的城市 — 求解全源最短路后统计满足阈值邻居数的城市，Floyd 经典应用。
• 1462. 课程表 IV — 有向图连通性传递闭包，Floyd 算法在布尔可达性上的变体。
• 2976. 转换字符串的最小成本 I — 字符转换图上的全源最短路径问题，利用 Floyd 预处理 26 个字母的最小代价。
• 2642. 设计可以添加边的图类 — 动态加边与单源/多源最短路径求解。
• 743. 网络延迟时间 — 单源最短路径基础，对比 Dijkstra 与 Floyd 的适用场景。

---

No.26 · 无向图最短路径条数

点击展开题目

给定一个包含 $n$ 个顶点（编号从 $0$ 到 $n-1$）的无向图，并用邻接矩阵表示顶点之间的距离。你需要计算从起始顶点 $s$ 到目标顶点 $t$ 的最短路径条数。

输入描述

• 整数 $n$（$1\le n\le 500$），表示图中顶点的数量；
• 整数 $s$（$0\le s < n$），表示起始顶点编号；
• 整数 $t$（$0\le t < n$），表示目标顶点编号；
• 邻接矩阵 $G$（二维数组形式给出），其中 $G[u][v] \ge 0$ 表示边权，$-1$ 表示 $u$ 与 $v$ 之间无直接连边。

输出描述

• 返回一个整数，表示从起始顶点 $s$ 到目标顶点 $t$ 的最短路径条数。

样例 1

输入

n = 4
s = 0
t = 2
G = [[0,2,-1,1],[2,0,1,-1],[-1,1,0,2],[1,-1,2,0]]

输出

2

解释： 图的拓扑结构与边权如下：

       0
     /   \
 (2)/     \(1)
   /       \
  1         3
   \       /
 (1)\     /(2)
     \   /
       2

从顶点 $0$ 到顶点 $2$ 的最短路径长度为 $3$，共有两条最短路径：

• 路径 1：$0 \to 1 \to 2$（长度 $2 + 1 = 3$）
• 路径 2：$0 \to 3 \to 2$（长度 $1 + 2 = 3$） 因此输出 2。

---

思路

普通的 Dijkstra 算法在贪心松弛过程中仅维护从起点出发到达各顶点的「最短路径长度」。本题要求在此基础上进一步计算「最短路径的方案数（条数）」。

由于边权为非负数，最短路径构成有向无环图（DAG），天然具备最优子结构性质，可以在 Dijkstra 距离松弛的同时，结合动态规划（DP）的加法原理与继承原理同步维护最短路径条数。

核心状态设计

1. d 数组：d[i] 表示当前已知的从源点 $s$ 到顶点 $i$ 的最短路径长度。初始化 $d[s] = 0$，其余顶点 $d[i] = \infty$。
2. pathCount 数组：pathCount[i] 表示当前从源点 $s$ 到顶点 $i$ 的最短路径条数。
   • 基础状态：起点到自身的路径只有 $1$ 条空路径，即 pathCount[s] = 1；
   • 其余所有顶点的方案数初始化为 $0$。
3. vis 数组：布尔数组，vis[i] 标记顶点 $i$ 的最短距离是否已由贪心策略最终确定。

算法流程（Dijkstra + 计数转移）

外层循环进行 $n$ 次：

1. 贪心选择：在所有尚未确定最短路的顶点中，挑选出当前距离最小的顶点 $u$（即 !vis[i] && d[i] < minD）。
   • 若找不到合法顶点（$u = -1$ 说明后续顶点均不可达），直接 break 结束算法。
   • 标记 vis[u] = true，固定其全局最短距离及最短路条数。
2. 状态转移（松弛与累加）： 枚举所有未确定的邻居 $v$（!vis[v] && G[u][v] >= 0）：
   • 情况一：发现更短路径（d[u] + G[u][v] < d[v]） 此时经由 $u$ 能取得更优的全局距离。之前累加到 $v$ 的旧路径全部作废，到达 $v$ 的最短路径必须经由 $u$。
     • 更新距离：d[v] = d[u] + G[u][v]
     • 覆盖方案数：pathCount[v] = pathCount[u]
   • 情况二：发现等长最短路径（d[u] + G[u][v] == d[v]） 此时经由 $u$ 到达 $v$ 的距离恰好等于当前已知最短路，说明发现了全新的最短路径组合。
     • 累加方案数：pathCount[v] += pathCount[u]

循环全部结束后，pathCount[t] 即为到达终点的最短路径总数（若不可达则为初始值 $0$）。

复杂度分析

• 时间复杂度：$O(n^2)$。采用朴素 Dijkstra 结构，双重循环各扫描 $n$ 次，对稠密矩阵是极优且常数极小的实现方式。
• 空间复杂度：$O(n)$。仅需维护长度为 $n$ 的距离数组 d、方案数数组 pathCount 与访问状态数组 vis。

---

C++

int countShortestPaths(int** G, int n, int s, int t) {
    const int INF = 0x3f3f3f3f;                 // 定义INF表示无穷大
    vector<int> d(n, INF);                      // d[i] 保存从 s 到 i 的最短距离
    vector<int> pathCount(n, 0);                // pathCount[i] 保存从 s 到 i 的最短路径条数
    vector<bool> vis(n, false);                 // vis[i] 标记顶点 i 的最短路是否已确定

    // 初始化起点状态
    d[s] = 0;
    pathCount[s] = 1;

    for (int k = 0; k < n; ++k) {
        int minD = INF;
        int u = -1;
        // 寻找当前未访问且距离最小的顶点 u
        for (int i = 0; i < n; ++i) {
            if (!vis[i] && d[i] < minD) {
                minD = d[i];
                u = i;
            }
        }
        // 若找不到连通的顶点，直接结束
        if (u == -1) {
            break;
        }
        vis[u] = true;                          // 标记 u 已确定最短距离

        // 遍历所有邻接点 v 进行松弛和路径计数
        for (int v = 0; v < n; ++v) {
            if (!vis[v] && G[u][v] >= 0) {
                if (d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];           // 更新更短距离
                    pathCount[v] = pathCount[u];     // 更新路径条数
                } else if (d[u] + G[u][v] == d[v]) {
                    pathCount[v] += pathCount[u];    // 累加等长路径
                }
            }
        }
    }

    return pathCount[t];                        // 返回最短路径条数
}

相似题目

• AcWing 1134. 最短路计数 — 本题的无权图原型题（出自 NOIP2011/洛谷 P1144），统计从源点到各点的最短路条数。
• AcWing 383. 观光 — 本题的带权进阶题，用 Dijkstra 同时求解最短路和次短路的条数。
• 1976. 到达目的地的方案数 — 本题的力扣对标原题，带权无向图最短路 Dijkstra + DP 计数。
• 743. 网络延迟时间 — 经典单源最短路径模板。
• 1514. 概率最大的路径 — 最优路径松弛思想拓展。
• 797. 所有可能的路径 — 有向无环图中的全部路径搜索与计数。
• 62. 不同路径 — 网格图上的加法原理路径计数基础。

---

No.25 · 无向图最短距离

点击展开题目

给定一个包含 $n$ 个顶点（编号从 $0$ 到 $n-1$）的无向图，并用邻接矩阵表示顶点之间的距离。你需要计算从起始顶点 $s$ 到目标顶点 $t$ 的最短距离。如果无法到达目标顶点，则返回 $-1$。

输入描述

• 整数 $n$（$1\le n\le 500$），表示图中顶点的数量；
• 整数 $s$（$0\le s < n$），表示起始顶点编号；
• 整数 $t$（$0\le t < n$），表示目标顶点编号；
• 邻接矩阵 $G$（二维数组形式给出），其中 $G[u][v] \ge 0$ 表示边权，$-1$ 表示 $u$ 与 $v$ 之间无直接连边。

输出描述

• 返回一个整数，表示从 $s$ 到 $t$ 的最短路径长度；若不可达则返回 $-1$。

样例 1

输入

n = 4
s = 0
t = 2
G = [[0,2,-1,4],[2,0,1,-1],[-1,1,0,3],[4,-1,3,0]]

输出

3

解释： 图的拓扑结构与边权如下：

       (2)
   0 -------- 1
    \        /
 (4) \      / (1)
      \    /
   3 -------- 2
       (3)

从顶点 $0$ 到顶点 $2$ 的最短路径为 $0 \to 1 \to 2$，总距离为 $2 + 1 = 3$（而经由 $3$ 的路径 $0 \to 3 \to 2$ 距离为 $4 + 3 = 7$）。

样例 2

输入

n = 3
s = 0
t = 2
G = [[0,1,-1],[1,0,-1],[-1,-1,0]]

输出

-1

解释： 图的拓扑结构与边权如下：

   0 -------- 1       2 (孤立点)
       (1)

顶点 $0$ 和顶点 $2$ 之间不连通，无法到达，因此返回 $-1$。

---

思路

本题是带非负权图的单源最短路径（Single-Source Shortest Path, SSSP）经典问题，因为边权均为非负数（无负权边/负权环），非常适合采用标准的 Dijkstra 算法 进行求解。

核心状态与数组

1. d 数组：长度为 $n$，$d[i]$ 表示当前已知的从起点 $s$ 出发到达顶点 $i$ 的最短路径长度。
   • 初始化时除 $d[s] = 0$ 外，其余顶点均置为极大值 $\infty$（如 0x3f3f3f3f）。
2. vis 数组：长度为 $n$，$vis[i]$ 记录顶点 $i$ 的最短路径是否已经确定（已完成贪心锁定）。
   • 初始化时所有顶点均为 false。

算法流程（贪心松弛）

每轮循环执行以下两步：

1. 寻找未固定的最小距离顶点： 在所有 !vis[i] 的顶点中，找出距离起点当前最近的顶点 $u$（即 $d[u]$ 最小）。
   • 若找不到合法顶点（$u = -1$ 说明其余顶点均不可达），或已提前找到目标点（$u = t$ 说明目标点的全局最短路径已固定），可直接 break 提前结束循环。
   • 将选出的顶点标记为确定：vis[u] = true。
2. 邻居松弛（Relaxation）： 遍历顶点 $u$ 的所有邻接点 $v$。如果 $G[u][v] \ge 0$ 且 !vis[v]：
   • 检查以 $u$ 为中介跳板能否缩短起点到达 $v$ 的路径长度，即若 $d[u] + G[u][v] < d[v]$，则更新 $d[v] = d[u] + G[u][v]$。

全部轮次结束（或提前退出）后，检查 $d[t]$ 是否仍为 $\infty$：若等于 $\infty$ 说明终点不可达返回 $-1$；否则直接返回 $d[t]$。

复杂度分析

• 时间复杂度：$O(n^2)$。朴素 Dijkstra 算法双重循环，外层循环 $n$ 次，内层分别线性扫描未访问顶点的最小值和枚举邻接边更新，对于本题 $n \le 500$ 的稠密图邻接矩阵，运算量仅约 $2.5 \times 10^5$ 次，瞬间完成。
• 空间复杂度：$O(n)$。仅需要维护长度为 $n$ 的距离数组 d 与访问状态数组 vis。

---

C++

int shortestDistance(int n, int s, int t, int** G) {
    const int INF = 0x3f3f3f3f;                      // 定义“无穷大”常量

    vector<int> d(n, INF);                           // d[i] 保存当前已知的从 s 到 i 的最短距离
    vector<bool> vis(n, false);                      // vis[i] 标记顶点 i 是否已是最短距离

    d[s] = 0;                                        // 起点到自己的距离为 0

    for (int k = 0; k < n; ++k) {
        int minD = INF;                              // 当前最小距离
        int u = -1;                                  // 最小距离对应的顶点
        for (int i = 0; i < n; ++i) {
            if (!vis[i] && d[i] < minD) {
                minD = d[i];
                u = i;
            }
        }
        if (u == -1 || u == t) {                     // 无可达新顶点或已到达目标，提前结束
            break;
        }
        vis[u] = true;                               // 标记顶点 u 为已访问

        for (int v = 0; v < n; ++v) {
            if (!vis[v] && G[u][v] >= 0) {           // 存在边且 v 尚未固定最短距离
                int newD = d[u] + G[u][v];          // 计算通过 u 到 v 的距离
                if (newD < d[v]) {
                    d[v] = newD;                    // 松弛操作：更新 d[v]
                }
            }
        }
    }

    return d[t] == INF ? -1 : d[t];                  // 目标不可达则返回 -1，否则返回最短距离
}

相似题目

• 743. 网络延迟时间 — 标准单源最短路径模板题，Dijkstra 算法实战。
• 787. K 站中转内最便宜的航班 — 带有边数/步数限制的最短路径进阶（Bellman-Ford / 限制步数 Dijkstra）。
• 1514. 概率最大的路径 — 乘积最大路径转换，Dijkstra 贪心思想应用。
• 1631. 最小体力消耗路径 — 网格图上的瓶颈最短路，Dijkstra 优先队列或二分+BFS。
• 1976. 到达目的地的方案数 — 在求解最短路径的同时进行方案数 DP 计数。

---

No.24 · 无向图层级顶点数量

点击展开题目

给定一个无向连通图的邻接矩阵 $G$ 和一个起始顶点 $s$。定义从 $s$ 出发到其他各顶点的「层号」为：从 $s$ 到该顶点的最短路径所经过的边数（$s$ 本身的层号为 $0$）。请按照层号从小到大的顺序，给出每一层的顶点数量。

输入描述

• 邻接矩阵 $G$（二维数组形式给出），表示无向连通图；
• 整数 $s$（$0\le s < n$），表示起始顶点的编号。

输出描述

• 返回一个整数数组，按层号从小到大依次表示每一层的顶点数量。

样例 1

输入

G = [[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]]
s = 0

输出

[1,2,1]

解释： 图的拓扑结构如下：

0 ----- 1
|     /
|   /
| /
2 ----- 3

从顶点 $0$ 出发：

• 层号 $0$：顶点 $0$（共 $1$ 个）
• 层号 $1$：顶点 $1$ 和 $2$（共 $2$ 个）
• 层号 $2$：顶点 $3$（共 $1$ 个） 因此结果为 $[1, 2, 1]$。

样例 2

输入

G = [[0,1,0,0],[1,0,1,0],[0,1,0,1],[0,0,1,0]]
s = 3

输出

[1,1,1,1]

解释： 图的拓扑结构如下：

0 ----- 1 ----- 2 ----- 3

从顶点 $3$ 出发：

• 层号 $0$：顶点 $3$（共 $1$ 个）
• 层号 $1$：顶点 $2$（共 $1$ 个）
• 层号 $2$：顶点 $1$（共 $1$ 个）
• 层号 $3$：顶点 $0$（共 $1$ 个） 因此结果为 $[1, 1, 1, 1]$。

思路

本题的核心是利用广度优先搜索（BFS）按层次向外扩展的天然特性：在无权图（或边权均为 $1$ 的图）中，BFS 首次访问到某个顶点时所经历的搜索轮数，严格等于从起点 $s$ 到该顶点的最短路径边数（即层号）。

• 算法设计（分层 BFS）：
  1. 状态初始化：创建大小为 $n$ 的布尔数组 visited，初始均为 false；创建 BFS 队列 q 以及存放各层节点数的结果数组 levelCount；
  2. 起点入队：将起始顶点 $s$ 标记为已访问（visited[s] = true），并推入队列 q；
  3. 分层遍历：当队列不为空时，当前队列中的全部节点恰好对应图中的同一「层」：
     • 获取当前队列长度 levelSize = q.size()，直接将其存入 levelCount；
     • 循环 levelSize 次，依次出队当前层的节点 $u$；
     • 检查节点 $u$ 在邻接矩阵中的所有邻接点 $v$（$0 \le v < n$）：若 $G[u][v] == 1$ 且 $v$ 未被访问过，则将 $v$ 标记为已访问并入队 q；
  4. 循环直至队列为空，此时图中的所有连通节点均已按最短距离分层处理完毕，返回 levelCount。
• 复杂度分析：
  • 时间复杂度：图以邻接矩阵形式存储，共 $n$ 个顶点，每个顶点出队时遍历一整行检查邻接关系（$n$ 次操作），总时间复杂度为 $O(n^2)$。
  • 空间复杂度：需要大小为 $n$ 的 visited 数组、BFS 队列以及存储层统计结果的容器，空间复杂度为 $O(n)$。

C++

vector<int> countLevel(int** G, int n, int s) {
    vector<bool> visited(n, false);          // 记录每个顶点是否访问过
    queue<int> q;                            // BFS 队列
    vector<int> levelCount;                  // 存放每一层顶点数量的结果

    visited[s] = true;                       // 标记起始顶点 s 为已访问
    q.push(s);                               // 将 s 入队

    // 按层遍历整个图
    while (!q.empty()) {
        int levelSize = (int)q.size();       // 当前队列大小即为当前层的顶点数
        levelCount.push_back(levelSize);

        for (int i = 0; i < levelSize; ++i) {
            int u = q.front(); q.pop();      // 取出当前层的一个顶点
            for (int v = 0; v < n; ++v) {
                if (G[u][v] == 1 && !visited[v]) {
                    visited[v] = true;       // 标记邻居 v 已访问
                    q.push(v);               // 将 v 入队
                }
            }
        }
    }

    return levelCount;
}

相似题目

• 102. 二叉树的层序遍历 — 经典分层 BFS 模板（通过记录 levelSize 按层处理）。
• 841. 钥匙和房间 — 图的连通性与广度优先遍历。
• 1091. 二进制矩阵中的最短路径 — 基于网格图的最短步数分层搜索。
• 1129. 颜色交替的最短路径 — 带状态的最短路径层级 BFS。
• 2608. 图中的最短环 — 多源/单源 BFS 维护节点层级与距离。

---

No.23 · 最大连通块

点击展开题目

给定一个无向图的邻接矩阵 $G$，该图共有 $n$ 个顶点（顶点编号为从 $0$ 到 $n-1$）。你需要计算图中顶点数量最多的连通块中的顶点数量。

输入描述

• 邻接矩阵 $G$（二维数组形式给出），表示无向图；
• 整数 $n$（$1\le n\le 500$），表示图中顶点的数量。

输出描述

• 返回一个整数，表示图中顶点数量最多的连通块中的顶点数量。

样例 1

输入

G = [[0,1,0],[1,0,0],[0,0,0]]

输出

2

解释： 图的拓扑结构如下：

0 ----- 1

2

图中包含两个连通块：

• 第一个连通块包含顶点 $0$ 和 $1$，大小为 $2$
• 第二个连通块只包含顶点 $2$，大小为 $1$ 因此最大连通块的大小为 $2$。

思路

本题是图论中经典的「求无向图连通块的最大顶点数」问题：

• 算法设计（深度优先搜索 DFS）：
  1. 访问标记：维护一个布尔数组 visited，记录顶点是否已被遍历过，初始全为 false；
  2. 遍历连通块：从编号 $0$ 到 $n-1$ 依次遍历顶点 $i$。若顶点 $i$ 尚未被访问，说明发现了一个新的连通块，初始化计数器 count = 0，以顶点 $i$ 为起点调用 DFS 遍历；
  3. DFS 扩展与计数：在 DFS(u, ...) 中：
     • 将当前顶点标记为已访问：visited[u] = true，连通块顶点数累加：count++；
     • 枚举顶点 $u$ 的所有可能邻居 $v$（$0\le v < n$）。若邻接矩阵显示有边相连（$G[u][v] == 1$）且 $v$ 未被访问过，则递归调用 DFS(v, ...) 继续统计该连通块内的所有可达节点；
  4. 维护最大值：每次 DFS 遍历完整一个连通块后，用当前连通块的大小 count 更新全局最大值 maxCount = max(maxCount, count)。
• 复杂度分析：
  • 时间复杂度：每个顶点最多被访问一次；每个顶点在 DFS 中需要扫描其一整行邻接矩阵（共 $n$ 个元素），总共有 $n$ 个顶点，因此总时间复杂度为 $O(n^2)$。
  • 空间复杂度：需要大小为 $n$ 的 visited 数组以及 DFS 递归调用栈（最坏情况下链式图深度为 $n$），空间复杂度为 $O(n)$。

C++

/**
 * @param G: 邻接矩阵，表示无向图，按二维数组的方式用下标即可访问内部元素
 * @param n: 图中顶点的数量
 * @return: 返回图中顶点数量最多的连通块中的顶点数量
 */

void DFS(int u, int** G, vector<bool>& visited, int n, int &count)
{
    visited[u] = true;
    count ++;
    for(int v = 0; v < n; v ++)
    {
        if(G[u][v] == 1 && !visited[v])
        {
            DFS(v, G, visited, n, count);
        }
    }
}

int largestConnectedComponent(int** G, int n) {
    vector<bool> visited(n, false);
    int maxCount = 0;
    for(int i = 0; i < n; i ++)
    {
        if(!visited[i])
        {
            int count = 0;
            DFS(i, G, visited, n, count);
            if(count > maxCount)
            {
                maxCount = count;
            }
        }
    }
    return maxCount;
}

相似题目

• 695. 岛屿的最大面积 — 网格图中的最大连通分量计数，DFS/BFS 核心模型。
• 547. 省份数量 — 经典邻接矩阵连通块遍历与计数。
• 827. 最大人工岛 — 连通块大小标记与合并扩展。
• 1971. 寻找图中是否存在路径 — 判断两点是否同属一个连通块。
• 1254. 统计封闭岛屿的数目 — 连通分量遍历与边界条件判定。

---

No.22 · 双子连通块

点击展开题目

给定一个无向图的邻接矩阵 $G$，该图共有 $n$ 个顶点（顶点编号为从 $0$ 到 $n-1$）。请你计算图中有多少个「双子连通块」。双子连通块是指恰好由两个顶点组成的连通块（即这两个顶点之间有边相连，且不与图中其他任何顶点相连）。

输入描述

• 邻接矩阵 $G$（二维数组形式给出），表示无向图；
• 整数 $n$（$1\le n\le 500$），表示图中顶点的数量。

输出描述

• 返回一个整数，表示图中双子连通块的数量。

样例 1

输入

G = [[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]]

输出

2

解释： 图的拓扑结构如下：

0 ----- 1

2 ----- 3

图中存在两个双子连通块：

• 顶点 $0$ 和 $1$ 构成的连通块
• 顶点 $2$ 和 $3$ 构成的连通块

样例 2

输入

G = [[0,1,1],[1,0,0],[1,0,0]]

输出

0

解释： 图的拓扑结构如下：

    0
   / \
  1   2

图中顶点 $0$ 的度为 $2$，$1$ 和 $2$ 的度均为 $1$，三者构成一个大小为 $3$ 的连通块，因此不存在双子连通块。

思路

本题的核心在于识别「大小恰好为 2 的连通块」在无向图中的图论等价条件：

• 充要条件转化： 在一个简单无向图中，一个连通分量恰好包含两个顶点 $u$ 和 $v$，当且仅当满足以下两个条件：
  1. 顶点 $u$ 与 $v$ 直接相连，即 $G[u][v] = 1$；
  2. 顶点 $u$ 与 $v$ 不与图中的任何其他顶点相连。这意味着 $u$ 和 $v$ 各自直接相连的边数恰好为 $1$，即 $\text{degree}[u] = 1$ 且 $\text{degree}[v] = 1$。 如果连通块顶点数大于 2，必然至少存在一个顶点的度数 $\ge 2$；若顶点度数为 0，则为孤立点。
• 算法设计：
  1. 统计顶点的度：遍历邻接矩阵，行求和计算出所有顶点的度数，存储在数组 degree 中：

     $$\text{degree}[i] = \sum_{j=0}^{n-1} G[i][j]$$

  2. 枚举候选边：双重循环遍历无序顶点对 $(i, j)$（$0\le i < j < n$）。若当前顶点 $i$ 的度数为 $1$，且存在与 $j$ 的连边（$G[i][j] == 1$）且顶点 $j$ 的度数也为 $1$，则找到了一个满足条件的双子连通块，计数加 1。
• 复杂度分析：
  • 时间复杂度：计算所有顶点度数耗时 $O(n^2)$，遍历顶点对枚举边耗时 $O(n^2)$，总时间复杂度为 $O(n^2)$。
  • 空间复杂度：需要一个大小为 $n$ 的数组 degree 存储度数，空间复杂度为 $O(n)$。

C++

/**
 * @param G: 邻接矩阵，表示无向图，按二维数组的方式用下标即可访问内部元素
 * @param n: 图中顶点的数量
 * @return: 返回图中双子连通块的数量
 */
int countTwinConnectedComponents(int** G, int n) {
    vector<int> degree(n);
    for(int i = 0; i < n; i ++)
    {
        degree[i] = 0;
        for(int j = 0; j < n; j ++)
        {
            degree[i] += G[i][j];
        }
    }

    int twinCount = 0;
    for(int i = 0; i < n; i ++)
    {
        if(degree[i] == 1)
        {
            for(int j = i + 1; j < n; j ++)
            {
                if(G[i][j] == 1 && degree[j] == 1)
                {
                    twinCount ++;
                }
            }
        }
    }
    return twinCount;
}

相似题目

• 2685. 统计完全连通分量的数量 — 统计具有特定结构（完全子图）的连通分量数量。
• 547. 省份数量 — 经典邻接矩阵连通分量计数（并查集或 BFS/DFS）。
• 1971. 寻找图中是否存在路径 — 判断两点是否在同一个连通块内。
• 1319. 连通网络的操作次数 — 考察连通分量数量与网络冗余边的关系。
• 841. 钥匙和房间 — 图的连通性与遍历。

---

No.21 · 度最大的顶点

点击展开题目

给定一个无向图的邻接矩阵 $G$，该图共有 $n$ 个顶点（顶点编号为从 $0$ 到 $n-1$）。图中顶点的度是指与该顶点直接相连的边的数量。请找出图中度最大的顶点编号。如果有多个顶点的度相同且都是最大的，则返回其中编号最小的那个。

输入描述

• 邻接矩阵 $G$（二维数组形式给出），表示无向图；
• 整数 $n$（$1\le n\le 500$），表示图中顶点的数量。

输出描述

• 返回一个整数，表示度最大的顶点编号。

样例 1

输入

G = [[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]]

输出

2

解释： 图的拓扑结构如下：

0 ----- 1
|     /
|   /
| /
2 ----- 3

各顶点的度分别为：

• 顶点 $0$：度 $2$（连接 $1, 2$）
• 顶点 $1$：度 $2$（连接 $0, 2$）
• 顶点 $2$：度 $3$（连接 $0, 1, 3$）
• 顶点 $3$：度 $1$（连接 $2$）

因此度最大的顶点是 $2$。

样例 2

输入

G = [[0,1,0],[1,0,1],[0,1,0]]

输出

1

解释： 图的拓扑结构如下：

0 ----- 1 ----- 2

各顶点的度分别为：

• 顶点 $0$：度 $1$（连接 $1$）
• 顶点 $1$：度 $2$（连接 $0, 2$）
• 顶点 $2$：度 $1$（连接 $1$）

因此度最大的顶点是 $1$。

思路

本题考察无向图的表示方式及「顶点的度」的基本概念：

• 基本性质：在无向图的邻接矩阵 $G$ 中，$G[i][j] = 1$ 表示顶点 $i$ 与顶点 $j$ 之间存在一条无向边，而 $G[i][j] = 0$ 表示无边。因为无向图没有方向之分，顶点 $i$ 的度（与该点直接相连的边数）恰好等于矩阵第 $i$ 行（或第 $i$ 列）中所有数值的总和：

  $$\text{degree}(i) = \sum_{j=0}^{n-1} G[i][j]$$

• 多解选取策略：题目要求若有多个顶点度数相同且同为最大，返回编号最小的顶点。我们遍历顶点编号 $i$ 从 $0$ 到 $n-1$：
  • 初始化 maxDegree = -1，maxVertex = 0；
  • 仅当当前顶点的度数严格大于当前最大值时（degreeCount > maxDegree）才更新 maxDegree 和 maxVertex；
  • 遇到相同度数时不做更新，天然保留了较早遇到的较小编号，无需额外排序或多重比较。
• 复杂度分析：
  • 时间复杂度：共有 $n$ 个顶点，每个顶点需扫描该行长为 $n$ 的元素计算度数，总时间复杂度为 $O(n^2)$。
  • 空间复杂度：仅使用常数个整型变量记录统计与答案，空间复杂度为 $O(1)$。

C++

/**
 * @param G: 邻接矩阵，表示无向图，按二维数组的方式用下标即可访问内部元素
 * @param n: 图中顶点的数量
 * @return: 度最大的顶点编号
 */
int findMaxDegreeVertex(int** G, int n) {
    int maxDegree = -1;
    int maxVertex = 0;
    for(int i = 0; i < n; i ++)
    {
        int degreeCount = 0;
        for(int j = 0; j < n; j ++)
            degreeCount += G[i][j];
        if(degreeCount > maxDegree)
        {
            maxDegree = degreeCount;
            maxVertex = i;
        }
    }
    return maxVertex;
}

相似题目

• 1791. 找出星型图的中心节点 — 中心节点与其余所有节点相连，度恰好为 $n-1$。
• 1615. 最大网络秩 — 基于每对顶点各自的度之和并减去重合边计算最大秩。
• 997. 找到小镇的法官 — 有向图中的入度与出度统计经典题。
• 1557. 可以到达所有点的最少点数目 — 统计入度为 $0$ 的起始顶点集合。
• 841. 钥匙和房间 — 图的连通性与度数遍历基础。

---

No.20 · 堆排序 - 降序版

点击展开题目

输入 $n$ 个正整数，使用堆排序算法将它们按从大到小的顺序进行排序，并输出初次建堆后的序列及堆排序过程中每轮得到的序列。

注：堆排序过程中均使用向下调整。

输入描述

• 第一行一个整数 $n$（$1\le n\le 100$），表示需要输入的正整数的个数；
• 第二行为用空格隔开的 $n$ 个正整数（每个正整数均不超过 $100$）。

输出描述

• 第一行输出初次建堆后的序列，每两个相邻的数之间用空格隔开；
• 接下来输出堆排序过程中每轮得到的序列，每行一个序列，每两个相邻的数之间用空格隔开。

样例 1

输入

5
2 8 5 1 3

输出

1 2 5 8 3
2 3 5 8 1
3 8 5 2 1
5 8 3 2 1
8 5 3 2 1

解释：

1. 初始填充完全二叉树：

      2
     / \
    8   5
   / \
  1   3

2. 建堆后的小根堆：

      1
     / \
    2   5
   / \
  8   3

3. 将 $3$ 和堆顶 $1$ 交换并向下调整后：

      2
     / \
    3   5
   / \
  8   1

4. 将 $8$ 和堆顶 $2$ 交换并向下调整后：

      3
     / \
    8   5
   / \
  2   1

5. 将 $5$ 和堆顶 $3$ 交换并向下调整后：

      5
     / \
    8   3
   / \
  2   1

6. 将 $8$ 和堆顶 $5$ 交换并向下调整后：

      8
     / \
    5   3
   / \
  2   1

思路

常规升序堆排序使用大根堆（每次将最大元素交换至末尾）；而本题要求从大到小（降序）排序，因此需要使用小根堆：

1. 建立小根堆（$O(n)$）：

   • 采用自底向上的向下调整（downAdjust）策略。
   • 完全二叉树中，最后一个非叶节点下标为 $\lfloor n/2 \rfloor$。从该节点开始向前遍历到根节点 $1$，依次执行向下调整。
   • downAdjust(low, high) 逻辑：在当前节点 $i$ 与其左右子节点中选出最小者；若子节点小于父节点，则交换并继续沿该分支向下调整，直到满足小根堆性质或到达边界。
   • 建堆完成后，堆顶元素即为全局最小值。输出当前序列。

2. 堆排序过程（$O(n \log n)$）：

   • 共进行 $n - 1$ 轮交换与调整（循环 $i$ 从 $n$ 递减至 $2$）：
     1. 将堆顶元素 heap[1]（当前堆中最小值）与当前堆末尾元素 heap[i] 交换，固定当前最小值在位置 $i$；
     2. 堆的有效规模缩减为 $i - 1$，对新的堆顶节点 $1$ 执行 downAdjust(1, i - 1)，恢复小根堆性质；
     3. 调整完成后，输出当前序列。
   • 经过 $n - 1$ 轮后，序列从后往前依次为第 1 小、第 2 小……即实现了从大到小的降序排序。

复杂度分析

• 时间复杂度：$O(n \log n)$。自底向上建堆的数学复杂度为 $O(n)$，后续 $n-1$ 次调整每次耗时 $O(\log n)$，总时间复杂度为 $O(n \log n)$。
• 空间复杂度：$O(1)$（不计输入数组本身），为原地排序（In-place sort）。

C++

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100 + 1;
int heap[MAXN];

// 向下调整：构造小根堆
void downAdjust(int low, int high) {
    int i = low, j = i * 2;
    while (j <= high) {
        if (j + 1 <= high && heap[j + 1] < heap[j]) {
            j = j + 1;            // 选出两个子节点中较小的那个
        }
        if (heap[j] < heap[i]) {
            swap(heap[j], heap[i]);  // 如果子节点比父节点小，则交换
            i = j; j = i * 2;
        } else {
            break;                // 堆结构已满足则退出
        }
    }
}

// 建堆，小根堆
void createHeap(int n) {
    for (int i = n / 2; i >= 1; i--) {
        downAdjust(i, n);      // 对每个非叶节点进行向下调整
    }
}

int main() {
    int n;
    scanf("%d", &n);          // 读取元素个数
    for (int i = 1; i <= n; i++) {
        scanf("%d", &heap[i]);  // 读取堆元素
    }

    // 初次建堆
    createHeap(n);
    for (int i = 1; i <= n; i++) {
        printf("%d", heap[i]);  // 输出建堆后的序列
        if (i < n) printf(" ");
    }
    printf("\n");

    // 堆排序过程：每轮将堆顶与末尾交换，再调整剩余部分
    for (int i = n; i > 1; i--) {
        swap(heap[1], heap[i]);    // 将最小元素放到尾部
        downAdjust(1, i - 1);      // 对剩余部分重新向下调整
        for (int j = 1; j <= n; j++) {
            printf("%d", heap[j]);  // 输出本轮排序结果
            if (j < n) printf(" ");
        }
        printf("\n");
    }

    return 0;
}

相似题目

• 912. 排序数组 — 经典手写堆排序/快速排序实战。
• 215. 数组中的第 K 个最大元素 — 堆排序思想的核心应用，维护 Top-K。
• 1046. 最后一块石头的重量 — 大根堆模拟贪心过程。
• 347. 前 K 个高频元素 — 利用小根堆维护出现频次最高的前 K 项。
• 451. 根据字符出现频率排序 — 堆排序与字符频次统计结合。

---

No.19 · 判断二叉堆

点击展开题目

给定一棵完全二叉树，判断这棵完全二叉树是否是堆。如果不满足堆的性质，返回 $0$；如果满足堆的性质，进一步判断是大顶堆（返回 $1$）还是小顶堆（返回 $2$）。

输入描述

• 一棵完全二叉树的根节点 root（通过 TreeNode 结构体给出）。

输出描述

• 返回 $0$（非堆）、$1$（大顶堆）或 $2$（小顶堆）。

样例 1

输入

root = [10,8,9,5,3,6,7]

输出

1

解释（满足大顶堆的性质）：

      10
     /  \
    8    9
   / \  / \
  5  3 6  7

样例 2

输入

root = [2,3,4,5,6,7,8]

输出

2

解释（满足小顶堆的性质）：

      2
     /  \
    3    4
   / \  / \
  5  6 7  8

样例 3

输入

root = [1,2,6,4,5,3]

输出

0

解释（既不是大顶堆，也不是小顶堆）：

      1
     /  \
    2    6
   / \  /
  4  5 3

思路

首先明确堆的定义：堆是一棵完全二叉树，其中所有节点均满足父子之间的大小关系。具体来说：

• 大顶堆：每个节点的值都大于或等于其子节点；
• 小顶堆：每个节点的值都小于或等于其子节点。

因此，我们只需对树进行一次遍历，检查每个节点是否满足上述性质，即可判断出是哪种堆。

我们分别定义两个标志变量：isMaxHeap 和 isMinHeap。初始时两者都为 true，表示当前树可能是大顶堆也可能是小顶堆。

在递归遍历的过程中，对于每个节点，分别检查它与左右子节点的值：

• 如果某个节点的值小于任意一个子节点的值，那么不满足大顶堆的定义，将 isMaxHeap 标记为 false；
• 如果某个节点的值大于任意一个子节点的值，那么不满足小顶堆的定义，将 isMinHeap 标记为 false。

通过这种方式持续向下遍历，如果发现某个时刻 isMaxHeap 和 isMinHeap 同时变为 false，说明该树不满足任何一种堆的定义，递归即可提前终止，减少不必要的计算。

递归函数遍历整棵树完成后，检查标志变量：

• 若 isMaxHeap 为 true，说明该树满足大顶堆（返回 $1$）；
• 若 isMinHeap 为 true，说明该树满足小顶堆（返回 $2$）；
• 若两个标志都为 false，说明既不是大顶堆也不是小顶堆（返回 $0$）。

复杂度：DFS 会访问树的每个节点一次，时间复杂度 $O(n)$（$n$ 为节点数）。递归调用栈深度最坏与树高相关；对于完全二叉树，树高为 $O(\log n)$，因此空间复杂度 $O(\log n)$。

C++

// 递归 DFS 辅助函数，检查与子节点的大小关系
void dfs(TreeNode* node, bool &isMaxHeap, bool &isMinHeap) {
    if (node == NULL || (!isMaxHeap && !isMinHeap)) {      // 到达叶子或不可能为任何堆时停止
        return;
    }

    if (node->left) {                                         // 检查左子节点
        if (node->val < node->left->val)  isMaxHeap = false;  // 父<左，不满足大顶堆
        if (node->val > node->left->val)  isMinHeap = false;  // 父>左，不满足小顶堆
    }

    if (node->right) {                                        // 检查右子节点
        if (node->val < node->right->val) isMaxHeap = false;  // 父<右，不满足大顶堆
        if (node->val > node->right->val) isMinHeap = false;  // 父>右，不满足小顶堆
    }

    dfs(node->left, isMaxHeap, isMinHeap);                   // 递归左子树
    dfs(node->right, isMaxHeap, isMinHeap);                   // 递归右子树
}

int isHeap(TreeNode* root) {
    bool isMaxHeap = true;   // 标记是否可能为大顶堆
    bool isMinHeap = true;   // 标记是否可能为小顶堆

    dfs(root, isMaxHeap, isMinHeap);                            // 从根开始检查

    if (isMaxHeap) return 1;  // 大顶堆
    else if (isMinHeap) return 2;  // 小顶堆
    else return 0;  // 既不是大顶堆也不是小顶堆
}

相似题目

• 1046. 最后一块石头的重量 — 经典大顶堆（优先队列）应用。
• 215. 数组中的第 K 个最大元素 — 堆排序 / 大顶堆选第 K 大。
• 703. 数据流中的第 K 大元素 — 小顶堆维护 Top-K。
• 347. 前 K 个高频元素 — 堆（优先队列）取前 K 项。
• 23. 合并 K 个升序链表 — 小顶堆合并多个有序序列。

---

No.18 · 判断完全二叉树

点击展开题目

给定一棵二叉树的根节点 $root$，判断这棵二叉树是否是完全二叉树。

完全二叉树的定义如下：

1. 除了最后一层外，其他层的节点数都达到最大值；
2. 最后一层的节点都集中在左侧。

输入描述

• 一棵二叉树的根节点 root（通过 TreeNode 结构体给出）。

输出描述 如果是完全二叉树返回 true，否则返回 false。

样例 1

输入

root = [1,2,3,4,5,6]

输出

true

解释：

    1
   / \
  2   3
 / \ /
4  5 6

这是一棵完全二叉树，因为：前两层节点数达到最大值；最后一层的节点全部靠左排列。

样例 2

输入

root = [1,2,3,4,5,null,6]

输出

false

解释：

    1
   / \
  2   3
 / \   \
4   5   6

这不是完全二叉树，因为第三层的节点 6 出现在空节点之后。

思路

判断一棵二叉树是否为完全二叉树的本质，就是检查树的各层节点是否满足两个条件：除了最后一层外，每层的节点必须是满的；而最后一层的节点则必须尽可能靠左，不能出现左侧有空节点而右侧却出现非空节点的情况。

所以最清晰、直观的解法就是采用 层序遍历（BFS）的方式，逐层从左到右扫描整棵树，按照定义依次检查节点排列是否满足完全二叉树的性质。

具体来说，我们维护一个队列 q，初始化时把根节点 root 加入队列中。然后开始循环执行以下操作：每次从队头取出一个节点：

• 如果取出的节点为空（即遇到空节点），则标记当前已经遇到过空节点，从这一刻起，后续队列中的节点都必须是空节点，否则就违背了完全二叉树的规则，也即后面不能再出现非空节点；
• 如果取出的节点不为空，且到目前为止还没有遇到过空节点，那么则将它的左右子节点（可能是空节点）依次加入队尾，以便继续检查后续节点；
• 如果取出的节点不为空，但已经遇到过空节点，那么说明违反完全二叉树的性质，直接返回 false 即可。

如果层序遍历能正常结束，那么说明过程中没有出现违反完全二叉树性质的情况，于是返回 true。

这种方法的时间复杂度为 $O(n)$（$n$ 为树的节点个数）。空间复杂度为 $O(n)$，最坏情况下队列可能存储树的最后一层节点，节点数最多接近 $n/2$。

C++

bool isCompleteTree(TreeNode* root) {
    queue<TreeNode*> q;               // 用于层序遍历的队列
    q.push(root);                     // 入队根节点

    bool foundNull = false;           // 标记是否已遇到空节点

    while (!q.empty()) {
        TreeNode* node = q.front();   // 取队头
        q.pop();                      // 出队

        if (node == NULL) {
            foundNull = true;         // 一旦遇到空节点，设置标记
        } else {
            if (foundNull) {          // 如果之前已遇到空节点
                return false;         // 但现在又遇非空节点，非完全二叉树
            }
            q.push(node->left);       // 左孩子入队
            q.push(node->right);      // 右孩子入队
        }
    }

    return true;                      // 完全二叉树
}

相似题目

• 958. 二叉树的完全性检验 — 与本题几乎完全同构（题面即此题）。
• 222. 完全二叉树的节点个数 — 利用完全二叉树结构特性加速计数。
• 102. 二叉树的层序遍历 — 本题 BFS 思路的基础模板。
• 662. 二叉树最大宽度 — 同样基于层序给节点编号，关注空节点位置。
• 199. 二叉树的右视图 — 层序遍历中关注每层特定位置节点。

---

No.17 · 森林中的最大树数

点击展开题目

森林由若干棵树组成，共 $n$ 个节点。现在给出 $m$ 组关系，每组关系指出节点 $a$ 和节点 $b$ 属于同一棵树。问森林中至多可能有多少棵树。

输入描述

• 第一行包含两个整数 $n$ 和 $m$（$1\le n\le 10^4$，$0\le m\le 10^4$），分别表示节点的总数量（节点编号从 $1$ 到 $n$）和关系数量；
• 接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$（$1\le a, b\le n$，$a\ne b$），表示节点 $a$ 和节点 $b$ 属于同一棵树。

输出描述 输出一个整数，表示森林中至多可能有多少棵树。

样例 1

输入

5 3
1 2
2 3
4 5

输出

2

解释：$1$、$2$、$3$ 属于同一棵树，$4$、$5$ 属于同一棵树，因此至多有两棵树。

思路

本题的核心是理解「森林中的树」与「连通块」的等价关系，并用并查集（Union-Find）维护连通性：

• 森林中每一棵树都是一个单独的连通块，题目问的「最多有多少棵树」实质上就是问「有多少个连通块」；
• 初始时每个节点自成一个集合，连通块（树）数量为 $cnt=n$，并令 parent[i] = i；
• 对每对关系 $(a, b)$ 执行合并：分别找到 $root_a$、$root_b$。若根不同，说明二者原本属于不同的树，合并后树的数量 $cnt$ 减少 $1$；若根相同，则已在同一棵树中，跳过；
• 处理完所有关系后，$cnt$ 即为连通块数量，也就是森林中树的最大数量。

时间复杂度 $O(m\cdot\alpha(n)+n)$（$\alpha(n)$ 为阿克曼反函数，实际可视为常数），空间复杂度 $O(n)$。

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int p[N];
int cnt;

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m;
    cin >> n >> m;
    cnt = n;
    for(int i = 1; i <= n; i ++)
        p[i] = i;
    
    while(m --)
    {
        int a, b;
        cin >> a >> b;
        if(find(a) != find(b))
        {
            p[find(a)] = find(b);
            cnt --;
        }
    }
    cout << cnt << "\n";
    return 0;
}

相似题目

• 547. 省份数量 — 连通块计数的经典模板，与本题几乎同构。
• 200. 岛屿数量 — 网格中的连通块计数，DFS/BFS 或并查集均可。
• 684. 冗余连接 — 并查集判定环，合并时检测同根。
• 1319. 连通网络的操作次数 — 同样基于连通块数与边的关系。
• 990. 等式方程的可满足性 — 并查集合并等价关系，再检测冲突。

---

No.16 · 二叉查找树的最值路径节点数

点击展开题目

给定一棵二叉查找树（BST），其中所有节点的值都是唯一的。请计算从树中值最小的节点出发，到值最大的节点的路径上，至少需要经过多少个中间节点（不包括最小和最大节点本身）。

输入描述

• 一棵二叉查找树的根节点 root（节点值唯一，通过 TreeNode 结构体给出）。

输出描述 返回从最小节点到最大节点的路径上中间节点的数量（不包括最小和最大节点本身）。

样例 1

输入

root = [3,1,4,null,2]

输出

1

解释：给定的 BST 结构如下：

    3
   / \
  1   4
   \
    2

• 最小节点是 $1$
• 最大节点是 $4$
• 从 $1$ 到 $4$ 的路径是 $1\to 3\to 4$，中间经过的节点是 $3$，共 $1$ 个节点

思路

本题的核心在于理解 BST 中最值节点的位置与最值之间的路径形态：

• 在 BST 中，最小值一定是最左节点——从根节点开始一直向左走，直到左子树为空；最大值一定是最右节点——从根节点开始一直向右走，直到右子树为空；
• 由于最小值位于根的左子树、最大值位于根的右子树，二者的最低公共祖先（LCA）必为根节点，因此从最小节点到最大节点的唯一简单路径必然经过根；
• 设根到最小节点的边数为 $d_1$（一路向左的步数），根到最大节点的边数为 $d_2$（一路向右的步数），路径上节点总数为 $d_1+d_2+1$（含根），去掉首尾的最小、最大节点，中间节点数即为 $d_1+d_2-1$；
• 边界：当树只有一个节点时，最小与最大节点重合（$d_1=d_2=0$），直接返回 $0$。

时间复杂度 $O(h)$（$h$ 为树高，最多各下降一次），空间复杂度 $O(1)$。

C++

/**
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */


/**
 * @param root: 二叉树的根节点
 * @return: 从最小节点到最大节点的路径上中间节点的数量（不包括最小和最大节点本身）
 */
int minMaxPathCount(TreeNode* root) {
    int d1 = 0;
    TreeNode* node = root;
    while(node->left != NULL)
    {
        node = node->left;
        d1 ++;
    }
    int d2 = 0;
    node = root;
    while(node->right != NULL)
    {
        node = node->right;
        d2 ++;
    }
    if(d1 + d2 == 0)
    {
        return 0;
    }
    return d1 + d2 - 1;
}

相似题目

• 98. 验证二叉搜索树 — 理解 BST 的左右有序性质，是本题的基础。
• 235. 二叉搜索树的最近公共祖先 — 同样利用 BST 有序性定位两节点路径与 LCA。
• 230. 二叉搜索树中第 K 小的元素 — 最小值节点即「第 1 小」，对应最左节点。
• 700. 二叉搜索树中的搜索 — 沿左/右方向下降导航，与本题找最值思路一致。
• 783. 二叉搜索树节点最小距离 — 同样围绕 BST 中序相邻（最小/最大）节点关系。

---

No.15 · 二叉查找树中序判定

点击展开题目

给定一个长度为 $n$ 的整数序列，判断该序列是否可能是某棵二叉查找树（BST）的中序遍历序列。

二叉查找树（BST）的定义如下：

• 对于任意结点，其左子树中所有结点的值都小于或等于该结点的值；
• 对于任意结点，其右子树中所有结点的值都大于该结点的值；
• 左右子树也必须是二叉搜索树。

输入描述

• 第一行一个整数 $n$（$1\le n\le 1000$），表示序列长度；
• 第二行包含 $n$ 个用空格分隔的整数 $a_i$（$1\le a_i\le 10^4$），表示给定的序列。

输出描述 如果该序列可能是某棵二叉查找树的中序遍历序列，输出 YES；否则输出 NO。

样例 1

输入

2
1 2

输出

YES

解释：可以构造如下二叉查找树，其中序遍历为 [1, 2]：

  2
 /
1

样例 2

输入

3
2 1 3

输出

NO

解释：无法构造出满足条件的二叉查找树。

思路

本题的核心在于利用二叉查找树的性质：BST 的中序遍历序列一定是（非严格）升序的。

• 由于左子树 $\le$ 根 $\le$ 右子树，且左右子树也满足 BST，整棵树的中序遍历必然单调不减；
• 反过来，任意一个单调不减的序列，都可以「取中段为根、左段为左子树、右段为右子树」递归构造出对应的 BST（相等值挂在左子树即可）；
• 因此判定等价于检查序列是否非递减：从左到右扫描，一旦出现 $a_i < a_{i-1}$ 即不合法。

时间复杂度 $O(n)$（一遍扫描），空间复杂度 $O(n)$（读入数组；也可边读边比做到 $O(1)$）。

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int n;

int main()
{
    cin >> n;
    a[0]= -1;
    bool flag = true;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        if(a[i] < a[i - 1]) flag = false;
    }
    cout << (flag ? "YES" : "NO") << "\n";
    return 0;
}

相似题目

• 98. 验证二叉搜索树 — 反过来：判断一棵给定树是否为 BST，同样依赖中序升序性质。
• 94. 二叉树的中序遍历 — 中序遍历的基础模板，是理解本题的前提。
• 700. 二叉搜索树中的搜索 — 利用 BST 有序性的典型操作。
• 701. 二叉搜索树中的插入操作 — 在保持 BST 性质下插入节点。
• 230. 二叉搜索树中第 K 小的元素 — 取中序遍历的第 k 个，直接利用升序性质。

---

No.14 · 树的层次和

点击展开题目

现有一棵 $n$ 个结点的树（结点编号为从 0 到 n-1，根结点为 0 号结点），每个结点有各自的权值 $w$。求这棵树每层的节点权值之和。

提示可以练习分别用层次遍历和先根遍历解决本题。

输入描述

• 第一行一个整数 $n$（$1\le n\le 10^{3}$），表示树的结点个数；
• 第二行 $n$ 个整数，分别给出编号从 0 到 n-1 的 $n$ 个结点的权值 $w$（$1\le w\le 10^{3}$）；
• 接下来 $n$ 行，按节点编号从小到大的顺序，每行给出一个结点的子结点编号列表，格式如下：

  k child_1 child_2 ... child_k

  其中 $k$（$0\le k\le n-1$）表示该结点的子结点个数，child_1…child_k 表示子结点的编号。

输出描述 输出 $m$ 行（$m$ 为层数），按层号从上到下的顺序，每层输出一个整数，表示该层的节点权值之和。

样例 1

输入

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

输出

1
2
12

解释：树的结构如下：

    0
    |
    1
   /|\
  2 3 4

• 第 1 层：只有节点 0，权值和为 1
• 第 2 层：节点 1，权值和为 2
• 第 3 层：节点 2、3、4，权值和为 3+4+5=12

思路

本题求「每层的节点权值之和」，本质是树的层次遍历（BFS），也可以先根遍历（DFS）配合深度标记来做。

BFS 解法（本题给出）

1. 用数组 nodes[N] 存储每个结点的权值 data 与子结点列表 children；下标即结点编号。
2. 将根结点 0 入队。
3. while 队列非空时，先用 levelSize = q.size() 记录当前层节点数，初始化 levelSum = 0；循环 levelSize 次：取出队首 u，将其权值累加进 levelSum，并把 u 的所有子结点入队。
4. 一层处理完即输出 levelSum（换行）。 关键在于「先记录层大小、再循环固定次数」的写法，确保一次循环只处理同一层的节点。

DFS 解法（提示） 先根遍历时额外携带「当前深度 depth」：进入结点时把 sum[depth] += data，再递归遍历子结点（深度 depth+1）。遍历结束后按 depth 从小到大输出 sum[] 即可。

复杂度：

• 时间复杂度：$O(n)$，每个结点入队/访问一次。
• 空间复杂度：$O(n)$，队列/递归栈最坏存 $O(n)$ 个结点。

C++ (BFS)

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

struct Node
{
  int data;
  vector<int> children;
} nodes[N];

int main()
{
  int n, k, child;
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> nodes[i].data;
  }
  for (int i = 0; i < n; i++)
  {
    cin >> k;
    for (int j = 0; j < k; j++)
    {
      cin >> child;
      nodes[i].children.push_back(child);
    }
  }

  queue<int> q;
  q.push(0);
  while(q.size())
  {
      int levelSize = q.size();
      int levelSum = 0;
      for(int i = 0; i < levelSize; i ++)
      {
          int u = q.front();
          q.pop();
          levelSum += nodes[u].data;

          for(int j = 0; j < nodes[u].children.size(); j ++)
          {
              q.push(nodes[u].children[j]);
          }
      }
      cout << levelSum << "\n";
  }

  return 0;
}

C++ (DFS)

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

struct Node
{
  int data;
  vector<int> children;
} nodes[N];

int levelSum[N];
int maxLevel;

void dfs(int u, int level)
{
    levelSum[level] += nodes[u].data;
    if(level > maxLevel) maxLevel = level;
    for(int i = 0; i < nodes[u].children.size(); i ++)
    {
        dfs(nodes[u].children[i], level + 1);
    }
}

int main()
{
  int n, k, child;
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> nodes[i].data;
  }
  for (int i = 0; i < n; i++)
  {
    cin >> k;
    for (int j = 0; j < k; j++)
    {
      cin >> child;
      nodes[i].children.push_back(child);
    }
  }

  dfs(0, 0);
  for(int i = 0; i <= maxLevel; i ++)
  {
      cout << levelSum[i] << "\n";
  }

  return 0;
}

相似题目

• 429. N 叉树的层序遍历 — 与本题同为多叉树按层遍历，思想一致。
• 102. 二叉树的层序遍历 — 二叉树版层次遍历，是本题基础。
• 637. 二叉树的层平均值 — 同样是按层聚合节点信息（求平均）。
• 515. 在每个树行中找最大值 — 每层聚合（取最大值）的变体。
• 199. 二叉树的右视图 — 层次遍历中关注每层特定位置节点。

---

No.13 · 判断满二叉树

点击展开题目

给定一棵二叉树的根节点 $root$，判断该二叉树是否是满二叉树。

满二叉树的定义：

• 二叉树的每个节点要么没有孩子，要么恰好有两个孩子；
• 所有的叶子都在同一层上。

样例 1

输入

root = [1,2,3,4,5,6,7]

输出

true

解释：二叉树结构如下：

    1
   / \
  2   3
 / \ / \
4  5 6  7

这棵二叉树是满二叉树。

样例 2

输入

root = [1,2,3,4,5,6]

输出

false

解释：二叉树结构如下：

    1
   / \
  2   3
 / \ /
4  5 6

节点 $3$ 只有一个孩子 $6$（缺右孩子），且叶子不在同一层，因此不是满二叉树。

思路

核心结论：高度为 $h$（根在第 $1$ 层）的满二叉树，节点总数一定恰好是 $2^h-1$。因此只需递归求出树的高度 $h$ 与节点总数 $n$，再验证 $n = 2^h-1$ 即可。

具体步骤：

1. 定义 dfs(node, height, count)：返回以 node 为根的子树的高度与节点数。
   • 空节点：height = count = 0。
   • 非空节点：递归求得左右子树的高度与节点数，则当前子树 height = max(左高, 右高) + 1，count = 左节点数 + 右节点数 + 1。
2. 对整棵树调用 dfs，得总高度 $h$ 与总节点数 $n$。
3. 判定 n == (1 << h) - 1（即 $2^h-1$）。

关于边界：叶子节点的左右均为空，故其 height = 1、count = 1，与「根在第 $1$ 层」的约定一致。空树（题目中通常约定返回 true，也由 root == nullptr 分支直接返回 true 处理）。

复杂度：时间复杂度 $O(n)$，每个节点访问一次；空间复杂度 $O(h)$，递归栈深度，最坏为树高。

C++

/**
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

/**
 * @param root: 二叉树的根节点
 * @return: 返回布尔值表示是否是满二叉树
 */
 void dfs(TreeNode* node, int& height, int& count)
{
    if(node == nullptr)
    {
        height = count = 0;
        return;
    }
    int leftHeight = 0, leftCount = 0;
    dfs(node->left, leftHeight, leftCount);
    int rightHeight = 0, rightCount = 0;
    dfs(node->right, rightHeight, rightCount);


    height = max(leftHeight, rightHeight) + 1;
    count = leftCount + rightCount + 1;
}


bool isFullTree(TreeNode* root) {
    if(root == nullptr) return true;
    int h = 0, n = 0;
    dfs(root, h, n);
    return n == (1 << h) - 1;
}

相似题目

• 222. 完全二叉树的节点个数 — 本题同样需要先求节点总数，是满二叉树判定的基石。
• 958. 二叉树的完全性检验 — 与满二叉树判定同属「树形态性质检验」。
• 110. 平衡二叉树 — 同样通过递归求子树高度来做性质判定。
• 104. 二叉树的最大深度 — 本题中 dfs 求得的高度即最大深度。
• 226. 翻转二叉树 — 二叉树递归遍历的基础模板。

---

No.12 · 二叉树的逆层序遍历

点击展开题目

给定一棵二叉树的根节点 $root$，返回该二叉树的「逆层序序列」。所谓「逆层序序列」是指按二叉树从上到下逐层遍历，每层按从右到左的顺序输出节点的值。

样例 1

输入

root = [1,2,3,null,null,4,5]

输出

[1,3,2,5,4]

解释：二叉树的结构如下：

    1
   / \
  2   3
     / \
    4   5

逆层序遍历的顺序为：第一层 $1$，第二层 $3$、$2$，第三层 $5$、$4$。

思路

标准层序遍历（BFS）天然就是「从上到下、逐层」地访问节点。要得到「每层从右到左」的顺序，只需在出队时先将该节点的右孩子入队、再将其左孩子入队——这样同层内后入队的左孩子会先被访问，等价于该层从右向左输出。

具体算法：

1. 若 root == NULL 直接返回空数组。
2. 用一个队列 q，初始放入 root。
3. 每次取出队首 current，将其值加入结果 res；先判右孩子非空则入队，后判左孩子非空则入队。
4. 队列空时结束，返回 res。

由于只是交换了左右孩子的入队顺序，整体仍是一次完整 BFS，时间 $O(n)$、空间 $O(n)$（队列最坏存满一层）。

复杂度：时间复杂度 $O(n)$，每个节点入队出队各一次；空间复杂度 $O(n)$，队列最多同时存一层节点。

C++

/**
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

/**
 * @param root: 二叉树的根节点
 * @return: 返回一个数组，表示逆层序遍历结果
 */
vector<int> reverseLevelOrder(TreeNode* root) {
    vector<int> res;
    if(root == NULL)
    {
        return res;
    }


    queue<TreeNode*> q;
    q.push(root);
    while(q.size())
    {
        TreeNode* current = q.front();
        q.pop();
        res.push_back(current->val);
        if(current->right != NULL)
        {
            q.push(current->right);
        }
        if(current->left != NULL)
        {
            q.push(current->left);
        }
    }
    return res;
}

相似题目

• 102. 二叉树的层序遍历 — 本题正序版，是逆层序的基础。
• 107. 二叉树的层序遍历 II — 自底向上层序遍历，方向变体。
• 103. 二叉树的锯齿形层序遍历 — 每层交替方向的层序遍历。
• 199. 二叉树的右视图 — 优先关注右侧节点的 BFS 实践。
• 429. N 叉树的层序遍历 — 队列层序遍历的拓展。

---

No.11 · 移除二叉树的叶节点

点击展开题目

给定一棵二叉树的根节点 $root$，你需要移除这棵树的所有叶节点。叶节点是指没有子节点的节点。移除叶节点后，如果新的叶节点产生，不需要再次移除（即只需要移除原始树的叶节点）。

样例 1

输入

root = [1,2,3,4,5]

输出

[1,2]

解释：原始二叉树如下：

    1
   / \
  2   3
 / \
4   5

原始叶节点为 $3$、$4$、$5$，将其移除后，树变为：

  1
 /
2

（节点 $2$ 原本不是叶节点，移除其子节点后沦为叶节点，按题意不再处理。）

思路

本题要求只删除原始树中的叶节点，删除后即使产生新的叶节点也不再处理。这等价于：遍历时只对「当前节点的直接孩子」做叶节点判定——若孩子是叶子则删除，否则继续向下递归；不向上回看保证了新产生的叶节点不会被二次删除。

采用深度优先搜索（递归）实现：

1. 递归边界：root == NULL 时直接返回。
2. 处理左子树：若 root->left 存在且其左右孩子均为空（即它是叶节点），则 delete root->left 并将其置空；否则递归 removeLeaf(root->left)。
3. 处理右子树：同理处理 root->right。

原始叶节点必在其父节点处被判定为叶子并删除；删除后沦为叶的内部节点不会再被其父节点回溯检查，因此恰好只移除一次、只移除原始叶节点，满足题意。

复杂度：时间复杂度 $O(n)$，每个节点最多访问一次；空间复杂度 $O(h)$，$h$ 为树高，即递归调用栈深度（最坏 $O(n)$，平衡时 $O(\log n)$）。

C++

/**
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

/**
 * @param root: 二叉树的根节点指针
 * @return: 无返回值，直接在原树上修改
 */
void removeLeaf(TreeNode* root) {
    if(root == NULL) return;


    //递归处理左子树
    if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
    {
        delete root->left;
        root->left = NULL;
    }else{
        removeLeaf(root->left);
    }


    if(root->right != NULL && root->right->left == NULL && root->right->right == NULL)
    {
        delete root->right;
        root->right = NULL;
    }else{
        removeLeaf(root->right);
    }
}

相似题目

• 1325. 删除给定值的叶子节点 — 按给定值删除叶节点的变体，思想高度相似。
• 814. 二叉树剪枝 — 按条件递归删除子树，递归删除思想一致。
• 1110. 删除节点并返回森林 — 删除指定节点并重构多棵树。
• 226. 翻转二叉树 — 二叉树递归遍历的基础模板。
• 257. 二叉树的所有路径 — 深度优先搜索遍历的经典实践。

---

No.10 · 二叉树节点值加一

点击展开题目

给定一棵二叉树的根节点 $root$，你需要对这棵二叉树进行修改：将每个节点的值都加 $1$。

提示你可以分别用先序遍历、中序遍历、后序遍历完成本题。

样例 1

输入

root = [1,2,3]

输出

[2,3,4]

解释：初始二叉树如下：

    1
   / \
  2   3

将每个节点的值加 $1$ 后，二叉树变为：

    2
   / \
  3   4

样例 2

输入

root = [4,2,6,1,3,5,7]

输出

[5,3,7,2,4,6,8]

解释：初始二叉树如下：

      4
     / \
    2   6
   / \ / \
  1  3 5  7

将每个节点的值加 $1$ 后，二叉树变为：

      5
     / \
    3   7
   / \ / \
  2  4 6  8

思路

本题要求对二叉树进行「每个节点值加 1」的修改。由于需要访问树中的每一个节点，本质上就是一次二叉树遍历。常见的先序、中序、后序三种遍历方式都可以完成本题，区别仅在于"对当前节点做修改"这一步被安排在递归序列中的哪个位置。

• 先序遍历（根 → 左 → 右）：先修改当前节点，再递归左子树，最后递归右子树。
• 中序遍历（左 → 根 → 右）：先递归左子树，再修改当前节点，最后递归右子树。
• 后序遍历（左 → 右 → 根）：先递归左子树，再递归右子树，最后修改当前节点。

无论哪种顺序，每个节点都恰好被访问一次，因此三者的时间复杂度均为 $O(n)$（$n$ 为节点总数），空间复杂度取决于递归深度即树的高度，最坏情况下退化为链 $O(n)$。

复杂度：时间复杂度 $O(n)$，空间复杂度 $O(h)$（$h$ 为树高，最坏 $O(n)$）。

C++

/**
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

/**
 * @param root: 二叉树的根节点
 * @return: 直接在原二叉树上修改，不需要返回
 */
 // 先序遍历 （根 → 左 → 右）
void plusOne(TreeNode* root) {
    if(!root) return;
    root->val += 1;
    plusOne(root->left);
    plusOne(root->right);
}
//中序遍历 （左 → 根 → 右）
void plusOne(TreeNode* root) {
    if(!root) return;
    plusOne(root->left);   // 先左子树
    root->val += 1;        // 再处理当前节点
    plusOne(root->right);  // 再右子树
}
//后续遍历（左 → 右 → 根）
void plusOne(TreeNode* root) {
    if(!root) return;
    plusOne(root->left);   // 先左
    plusOne(root->right);  // 再右
    root->val += 1;        // 最后处理当前节点
}

相似题目

• 226. 翻转二叉树 — 同样基于遍历对每个节点做局部修改（交换左右子树）。
• 144. 二叉树的前序遍历 — 本题先序实现的基础遍历模板。
• 94. 二叉树的中序遍历 — 中序遍历模板。
• 145. 二叉树的后序遍历 — 后序遍历模板。
• 617. 合并二叉树 — 同时遍历两棵树并对节点做合并修改。

---

No.9 · 矩阵中的全向块

点击展开题目

给定 $n$ 行 $m$ 列的 $0/1$ 矩阵。若两个 $1$ 在水平、垂直或对角线方向（共 8 个方向）上相邻，则认为这两个 $1$「连通」；连通关系具有传递性。所有连通的 $1$ 构成一个「全向块」。求矩阵中全向块的个数。

• 输入：首行 $n\ m$（$2\le n,m\le 100$），随后 $n$ 行每行 $m$ 个 0/1（空格隔开）。
• 输出：一个整数，表示全向块的个数。

样例 1

输入：
6 7
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
输出：
3

解释：矩阵中的 1 共形成 3 个块。

思路

思路：BFS 八连通块计数（经典「岛屿数量」的八连通版）

逐格扫描矩阵。当遇到一个值为 1 且未被访问过的位置时，说明发现了一个新的「全向块」——计数器加 1，并以该位置为起点做一次 BFS，把与它连通的所有 1 全部标记为已访问，避免后续重复计数。

八方向偏移

用一个长度为 8 的方向数组表示上、下、左、右及四个对角线方向（代码中 dx/dy 即这 8 个方向的行列偏移，顺序不同但覆盖相同 8 个方向）。BFS 每弹出一个位置，就遍历这 8 个方向，算出相邻坐标 (nextX, nextY)。

BFS 流程

• 起点入队并标记 inQueue；
• 只要队列非空：取队首 (x, y) 出队，检查 8 个相邻位置；若满足 canVisit（在矩阵内、值为 1、未访问），则标记入队；
• 队列清空时，当前块的所有 1 已被完整访问，回到主循环继续扫描。

复杂度：每个位置至多入队一次，时间复杂度 $O(n\times m)$；inQueue 与 matrix 均为 $n\times m$，空间复杂度 $O(n\times m)$。在 $n,m\le 100$ 下完全可行。

C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> Position;
const int N = 110;
int n, m, matrix[N][N];
bool inQueue[N][N] = {false};

const int M = 8;
int dx[M] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[M] = {-1, 0, 1, 1, 1, 0, -1, -1};

bool canVisit(int x, int y)
{
    return x >= 0 && x < n && y >= 0 && y < m
        && matrix[x][y] == 1
        && !inQueue[x][y];
}

void BFS(int x, int y)
{
    queue<Position> q;
    q.push(Position(x, y));
    inQueue[x][y] = true;
    while(q.size())
    {
        Position front = q.front();
        q.pop();
        for(int i = 0; i < M; i ++)
        {
            int nextX = front.first + dx[i];
            int nextY = front.second + dy[i];
            if(canVisit(nextX, nextY))
            {
                inQueue[nextX][nextY] = true;
                q.push(Position(nextX, nextY));
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cin >> matrix[i][j];

    int counter = 0;
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            if(matrix[i][j] == 1 && !inQueue[i][j])
            {
                BFS(i, j);
                counter ++;
            }
        }
    }

    cout << counter << "\n";
    return 0;
}

相似题目

• AcWing 1097 池塘计数：八连通块计数，思路几乎完全一致，可当作同题练手。
• LeetCode 200 岛屿数量（Number of Islands）：四连通版，BFS/DFS 连通块计数思想同源。
• LeetCode 695 岛屿的最大面积（Max Area of Island）：连通块遍历的变形，顺带练习面积统计。

---

No.8 · 奇数子集

点击展开题目

给定正奇数 $n$，令序列 $S=[1, 3, 5, \dots, n]$（即不超过 $n$ 的所有正奇数）。求 $S$ 的所有子集。

• 输入：一个正奇数 $n$（$1\le n\le 21$）。
• 输出：每个子集一行，输出所有子集。
  • 输出顺序：(1) 元素个数少的子集优先；(2) 元素个数相同时，按升序字典序升序（即逐元素比较，前 $k-1$ 项相同则比第 $k$ 项小的优先）。
  • 子集内部按升序输出，数之间用空格隔开，行末无多余空格；空集用空行表示；不允许重复子集。

样例 1

输入：1
输出：
1

样例 2

输入：3
输出：
1
3
1 3

思路

核心转化：把"奇数子集"变成"连续正整数子集"

$n$ 是第 $m=\lfloor n/2\rfloor+1$ 个正奇数，所以序列 $S=[1,3,\dots,n]$ 与 $[1,2,\dots,m]$ 一一对应（第 $i$ 个奇数 $=2i-1$）。于是只需先求连续序列 $[1,2,\dots,m]$ 的所有子集，输出时把每个元素乘 $2$ 减 $1$ 还原成奇数即可，问题被大幅简化。

DFS 枚举子集

定义 temp 保存当前子集，result 收集所有子集。dfs(idx) 表示处理到第 idx 个数：

• 若 idx == m+1，说明 $1..m$ 已决策完毕，把 temp 加入 result；
• 否则对第 idx 个数尝试选与不选两种分支：选则把 idx 压入 temp 后递归，递归返回后 pop_back 撤销；不选则直接递归下一个位置。这样完整遍历了所有 $2^m$ 个子集，且 temp 天然按升序生成。

排序满足输出顺序

收集完所有子集后按自定义 cmp 排序：先比元素个数（少的优先），个数相同再用 vector 自带的 <（逐元素字典序）比较。题目规则 (2) 的"前缀相同比第 $k$ 项"正是字典序的定义，a < b 天然满足，无需手写逐位比较。

输出细节：子集内已升序，按 j < size-1 控制空格避免行末多余空格；空集 temp 为空，循环不输出数字、只输出换行，即空行。

复杂度：$m=\Theta(n)$，子集总数 $2^m$，枚举与排序均为 $O(2^m)$ 量级；空间上 result 存全部子集 $O(2^m\cdot m)$。因 $n\le 21\Rightarrow m\le 11$，规模很小，完全可行。

C++

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> result;
vector<int> temp;
int n, m;

void dfs(int idx)
{
    if(idx == m + 1)
    {
        result.push_back(temp);
        return;
    }

    temp.push_back(idx);
    dfs(idx + 1);
    temp.pop_back();
    dfs(idx + 1);
}

bool cmp(const vector<int> &a, const vector<int> &b)
{
    if(a.size() != b.size())
        return a.size() < b.size();
    else
        return a < b;
}

int main()
{
    cin >> n;
    m = n / 2 + 1;
    dfs(1);
    sort(result.begin(), result.end(), cmp);

    for(int i = 0; i < result.size(); i ++)
    {
        for(int j = 0; j < result[i].size(); j ++)
        {
            cout << result[i][j] * 2 - 1;
            if(j < result[i].size() - 1)
            {
                cout << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}

相似题目

• LeetCode 78 Subsets：求一个集合的所有子集，本体的直接原型。
• LeetCode 90 Subsets II：含重复元素时的子集枚举，多一层去重思考。
• AcWing 92 递归实现指数型枚举：DFS「选/不选」枚举子集的经典模板题。

---

No.7 · 相邻不等重排

点击展开题目

给定长度为 $n$ 的整数数组，判断是否存在一种重排方式，使得重排后数组中任意相邻元素不相等。存在输出 Yes，否则输出 No。

• 输入：首行 $n$，次行 $n$ 个整数 $a_i$（$1\le a_i\le 10^5$）。
• 输出：Yes 或 No。

样例 1

输入：
3
1 1 2
输出：
Yes

解释：可重排为 [1, 2, 1]，相邻元素均不相等。

样例 2

输入：
4
1 1 1 2
输出：
No

解释：元素 1 出现 3 次，无法避免相邻重复。

思路

核心思路：问题等价于判断"出现次数最多的元素是否过多"。

要让重排后任意相邻元素不同，限制条件完全由出现次数最多的那个值决定——只要它不相邻，其余值自然更容易错开（可把它插进其余值形成的空隙中）。

判定条件：设数组长度 $n$，最频繁元素的出现次数为 maxCount，若能重排则必有

$$\text{maxCount}\le \left\lfloor\frac{n+1}{2}\right\rfloor$$

即代码中的 maxCount <= n + 1 >> 1（注意 >> 优先级低于 <=，实际等价于 (maxCount <= ((n+1)>>1))，正是向下取整除法）。满足则 Yes，否则 No。

为什么成立（鸽巢原理）：把出现最频繁的元素记为 $x$，共 $k$ 个。要把它们排得互不相邻，需要"其他元素"隔开。先摆出 $k$ 个 $x$，它们周围共有如下插入位（用 _ 表示）：

[前]  x  _  x  _  x  _  ...  _  x  [后]

• $k$ 个 $x$ 之间，有 $k-1$ 个内部空隙（必须填，否则两个 $x$ 贴在一起）；
• 再加上最前面和最后面 2 个端部位置。

因此插入位总数是 $(k-1)+2 = \mathbf{k+1}$ 个。

关键区别：这 $k+1$ 个位置不是都要填满。要满足"$x$ 互不相邻"，只有那 $k-1$ 个内部空隙是强制的——两端可以空着（空着表示 $x$ 排在首/末位，左边/右边无元素，谈不上相邻）。所以最少需要 $k-1$ 个"其他元素"去填充强制空隙。

易错点：若误以为全部 $k+1$ 个位置都必须填满，会得到过严的 $n-k\ge k+1$，进而误判。例如 $n=3,\ [1,1,2]$ 时 $k=2$，按"全填"会错判为 No；但只需 $k-1=1$ 个分隔符即可排成 [1,2,1]，正确答案是 Yes。口诀：$k+1$ 是总数，$k-1$ 才是必填名额。

其余元素一共有 $n-k$ 个，必须够填这 $k-1$ 个强制空隙：

$$n-k \ge k-1 \;\Rightarrow\; n+1 \ge 2k \;\Rightarrow\; k \le \left\lfloor\frac{n+1}{2}\right\rfloor$$

一旦 maxCount 超过这个上界，强制空隙填不满，必然有两个 $x$ 相邻，重排不可能。

复杂度：一次遍历统计频率并维护 maxCount，时间复杂度 $O(n)$，空间复杂度 $O(V)$（$V=10^5$ 为值域，用定长数组 freq 计数）。

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], freq[N], n;

int main()
{
    cin >> n;
    int maxCount = 0;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
        freq[a[i]] ++;
        maxCount = max(maxCount, freq[a[i]]);
    }
    cout << ((maxCount <= n + 1 >> 1) ? "Yes" : "No") << "\n";
    return 0;
}

相似题目

• LeetCode 767 Reorganize String：重排字符串使相邻字符不同，核心判定（最频字符 ≤ ⌊(n+1)/2⌋）与本題完全一致。
• LeetCode 1054 Distant Barcodes：高频元素插空排列，同样的"最频繁元素受限"思路。
• 拓展练习：优先队列 / 奇偶位置穿插写法，可加深对本判据的理解。

---

No.6 · 简单后缀表达式

点击展开题目

给定一个后缀表达式（逆波兰表达式）字符串，只包含数字字符 0–9、加号 +、乘号 *，计算其值。

计算规则（用栈模拟）：初始数组为空，依次处理每个字符——

1. 遇到数字：转成整数，追加到数组末尾；
2. 遇到 +：弹出末尾两个元素求和，结果追加回去；
3. 遇到 *：弹出末尾两个元素求积，结果追加回去。

处理完后数组唯一元素即答案。

• 输入：长度 $1\sim 20$ 的字符串，仅含 0–9、+、*。
• 输出：一个整数，结果保证在 int 范围内。

样例 1

输入：34+5*
输出：35

解释：[3]→[3,4]→+ 得 [7]→[7,5]→* 得 [35]。

样例 2

输入：99*
输出：81

解释：[9]→[9,9]→* 得 [81]。

思路

核心思路：用栈模拟逆波兰表达式求值。

后缀表达式的好处是无需考虑运算符优先级，从左到右扫描即可：操作数直接入栈，遇到运算符就"消费"栈顶的两个操作数做运算，结果再压回栈。

具体做法：

1. 遍历字符串每个字符 c：
   • 若是数字（isdigit(c) 为真），将 c - '0' 入栈（单字符数字直接转成对应整数）。
   • 若是运算符（+ 或 *），依次弹出栈顶两个元素：op1 = 弹出第一个、op2 = 弹出第二个，按运算符执行 op1 + op2 或 op1 * op2，把结果压回栈。
2. 扫描结束后，栈中仅剩一个元素，即表达式的值，输出 stk.top()。

关于操作数顺序：这里先弹出的是 op1（原栈顶，即后入的操作数），后弹出的是 op2（较早入的操作数）。由于本题运算符只有 + 和 *，两者都满足交换律，顺序不影响结果；若是减法或除法则需严格区分（先弹出的为右操作数）。

复杂度：每个字符只入栈/出栈一次，时间复杂度 $O(L)$（$L$ 为字符串长度，$\le 20$）；栈中最多同时存 $O(L)$ 个元素，空间复杂度 $O(L)$。

C++

#include <bits/stdc++.h>
using namespace std;
string str;
int res;
stack<int> stk;

int main()
{
    cin >> str;
    for(int i = 0; i < str.size(); i ++)
    {
        char c = str[i];
        if(isdigit(c))
        {
            stk.push(c - '0');
        }
        else
        {
            int op1 = stk.top();
            stk.pop();
            int op2 = stk.top();
            stk.pop();
            if(c == '+') stk.push(op1 + op2);
            else stk.push(op1 * op2);
        }
    }
    int res = stk.top();
    cout << res << "\n";
    return 0;
}

相似题目

• LeetCode 150 Evaluate Reverse Polish Notation：逆波兰表达式求值，与本体几乎同题（本题仅限 +、*）。
• AcWing 3302 表达式求值：中缀表达式求值，可对比学习栈在表达式解析中的用法。

---

No.5 · 减半递增

点击展开题目

给定长度为 $n$ 的数组（$n$ 为 $2$ 的幂，$1\le n\le 2^{16}$）。每次操作可删除当前数组的前半部分或后半部分。通过若干次操作后，希望剩余部分严格递增，且保留的元素尽可能多。求可保留的最大长度。

• 输入：首行 $n$，次行 $n$ 个整数 $a_i$（$1\le a_i\le 10^5$）。
• 输出：一个整数，表示可保留的最大长度。

样例 1

输入：
4
1 2 3 4
输出：
4

解释：数组已严格递增，长度 $4$。

样例 2

输入：
8
5 6 7 8 1 2 4 3
输出：
4

解释：删后半部分，保留 [5,6,7,8]，长度 $4$。

样例 3

输入：
4
4 3 2 1
输出：
1

解释：每次删一半，最终仅能保留 $1$ 个元素。

思路

核心思路：分治递归，把"只能整段删除一半"的约束转化为"每次把区间二分"。

每次操作删除前半或后半，等价于：最终保留的一定是某次二分后某个完整的子区间（因为不允许从中间挖掉一块，只能整半整半地砍）。于是在整个数组上，我们要找到一个完整子区间尽可能长且严格递增。

递归定义：dfs(l, r) 表示区间 $[l, r]$ 内可保留的最大严格递增长度。

1. 判断当前区间是否严格递增：isIncrease(l, r) 从左到右扫一遍，只要出现 a[i] <= a[i-1] 就不严格递增。若严格递增，直接返回区间长度 r - l + 1（已最优，无需再分）。
2. 否则二分：从 mid = (l + r) / 2 处切成 $[l, mid]$ 和 $[mid+1, r]$ 两半，递归求两半各自能保留的最大长度，取 max 作为本区间答案。
3. 入口 dfs(0, n-1) 即全局答案。

为什么正确：任何"保留段"都可由不断对半砍得到，因此它必然等于某个递归叶子/中途节点的完整区间。递归穷举了所有合法保留段（且不重不漏），取最长者即得最优。

复杂度：每次递归把区间对半分，深度为 $\log_2 n = 16$；每个节点判断递增最坏 $O(\text{区间长})$，整棵树各节点区间长之和恰为 $O(n)$（每层区间拼起来覆盖整个数组），因此总时间复杂度 $O(n\log n)$。空间主要取决于递归调用栈，最大深度 $\log_2 n$，故空间复杂度 $O(\log n)$。

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 16;
int a[N];
int n;

bool isIncrease(int l, int r)
{
    for(int i = l + 1; i <= r; i ++)
    {
        if(a[i] <= a[i - 1])
        {
            return false;
        }
    }
    return true;
}

int dfs(int l, int r)
{
    if(isIncrease(l, r)) return r - l + 1;
    int mid = l + r >> 1;
    return max(dfs(l, mid), dfs(mid + 1 ,r));
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    int result = dfs(0, n - 1);
    cout << result << "\n";
    return 0;
}

相似题目

• LeetCode 674 Longest Continuous Increasing Subsequence：最长连续递增子段，本体的基础形态（无"整段删半"约束）。
• LeetCode 53 Maximum Subarray：分治求解区间最值，与本题 dfs 二分思想同源。
• 拓展：含"只能整段删一半"约束的变体，可训练把操作约束翻译成区间划分的能力。

---

No.4 · 生成对称链表

点击展开题目

给定一个带头节点的单链表，要求以链表的最后一个节点为对称点，将链表中每个节点在对称点右侧对应位置复制出一个新节点。最终生成的新链表应当关于原链表尾节点对称。

即：原链表为 head → a₁ → a₂ → … → aₘ，处理后应为 head → a₁ → a₂ → … → aₘ → aₘ₋₁ → … → a₁。

函数签名（C++，原地修改，无返回值）：

void makeSymmetric(ListNode* head);

样例 1

输入：head = [3,4,1]
输出：[3,4,1,4,3]

解释：以尾节点 1 为对称中心，把 4、3 依次对称复制到 1 右侧，得到 head → 3 → 4 → 1 → 4 → 3。

样例 2

输入：head = [1,2,3,4]
输出：[1,2,3,4,3,2,1]

解释：以尾节点 4 为对称中心，把 3、2、1 依次复制到右侧，得到 head → 1 → 2 → 3 → 4 → 3 → 2 → 1。

思路

核心思路：先锁定对称中心（尾节点），再从前往后逐个"镜像复制"插到尾节点之后。

要让链表关于尾节点对称，等价于：保留原链表前半段不动，再把前半段（除尾节点本身外）逆序接在尾节点之后。

两步实现：

1. 找对称中心：定义指针 p 从第一个有效节点 head->next 出发，沿 next 走到 p->next == NULL，此时 p 停在最后一个有效节点（即对称中心）。p 的位置此后固定不变。
2. 镜像复制：再用指针 q 从 head->next 出发，当 q != p 时循环（即只复制到尾节点之前，尾节点自身不复制）：
   • 用 q->val 新建一个节点 newNode；
   • 把它头插到 p 之后：newNode->next = p->next; 再 p->next = newNode;
   • 因为 p 永远是对称中心，newNode 总是插在已插入副本的最前面——每次插入都把新副本顶到 p 紧邻的右侧，于是原顺序的 a₁,a₂,… 被倒着排成 …,a₂,a₁，自然形成对称结构。
   • q 前进一步，继续处理下一个原节点。

循环结束时，尾节点右侧依次挂着 aₘ₋₁, …, a₁，整条链表即关于尾节点对称。

复杂度：每个原节点最多复制一次，且只做了两次完整遍历（找尾一次、复制一次），因此时间复杂度为 $O(n)$（$n$ 为原链表长度）；额外新建了与原链表节点数（除去尾节点）相同数量的节点，空间复杂度为 $O(n)$。

C++

/**
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

/**
 * @param head: 链表的头节点，下一个节点是第一个有效节点
 * @return: 无返回值，直接在原链表上修改
 */
void makeSymmetric(ListNode* head) {
    ListNode* p = head -> next;        // 从第一个有效节点开始
    while(p->next != NULL)             // 遍历至尾节点
        p = p->next;

    ListNode* q = head->next;          // 从第一个有效节点重新开始
    while(q != p)                      // 遍历至尾节点前
    {
        ListNode* newNode = new ListNode(q->val); // 创建当前节点的副本
        newNode->next = p->next;       // 将新节点指向中心节点后
        p->next = newNode;             // 插入到中心节点之后
        q = q->next;                  // 移动到下一个原节点
    }
}

相似题目

• LeetCode 234 Palindrome Linked List：判断链表是否回文，同样依赖"对称中心 + 反转/复制后半"的思路。
• LeetCode 206 Reverse Linked List：链表反转，是「镜像/对称复制」的基础功。
• 拓展：原地复制、镜像链表、回文拼接类题目，可举一反三。

---

No.3 · 元素唯一化

点击展开题目

给定长度为 $n$ 的整数数组 $a$。允许对每个元素做至多一次调整：将值增加、减少或不变，但变化幅度最多为 $1$。

问是否存在一种调整方案，使得调整后所有元素两两互不相同。存在输出 Yes，否则输出 No。

• 输入：首行 $n$，次行 $n$ 个整数 $a_i$（$0\le a_i\le 10^5$）。
• 输出：Yes 或 No。

样例 1

输入：
3
5 5 5
输出：
Yes

解释：可调整为 $[4, 5, 6]$，三个元素互不相同。

样例 2

输入：
4
0 0 0 0
输出：
No

解释：无论怎么调整，$0$ 最多变到 $-1/0/1$，四个数无法全部互异。

思路

核心思路：排序后从左到右贪心，每个数取"能取到的最小且不重复的值"。

调整只能让每个数在 $\{x-1,\,x,\,x+1\}$ 中选一个，且最终要互不相同。要留给后面的数尽量多的空间，理想策略是：当前数在满足"严格大于前一个已确定数"的前提下，尽可能取小的值。

具体做法：

1. 先将数组排序（下标从 $1$ 开始），并设哨兵 a[0] = -2，保证第一个元素（a[1]，初始 $\ge 0$）一定满足 $> a[0]$。
2. 从左到右遍历每个 $a_i$，依次尝试三个候选增量 {-1, 0, +1}（即候选值 $a_i-1,\ a_i,\ a_i+1$）。一旦某个候选值严格大于前一个已经确定的数 a[i-1]，就把它定为 $a_i$ 的新值并停止尝试（因为按这个顺序，第一个满足条件的就是"最小可行值"）。
3. 若三个候选全部 $\le a[i-1]$（说明无论怎么调都和前一个数撞上），则无解，直接输出 No 并退出。
4. 全部遍历通过则说明可全部互异，输出 Yes。

为什么正确：排序后只需关心"与前一个不重复"——只要每个数都严格大于前一个，整条序列自然严格递增、必然两两不同。每次取最小可行值，能最大程度压低当前数，给右侧数字保留更充裕的取值范围，不会因当前贪大而误判无解。时间复杂度 $O(n\log n)$（瓶颈在排序），空间 $O(1)$。

补充：样例 2 中四个 $0$，排序后依次为 $0,0,0,0$；第一个取 $0$（哨兵 $-2$ 不挡），第二个最小可行是 $1$，第三个需 $>1$ 最小取 $2$，第四个需 $>2$ 最小取 $3$——但 $0$ 最多只能调整到 $1$，取不到 $3$，于是第三步失败输出 No，符合预期。实际上当某个值连续出现过多（同一原始值出现超过 $3$ 次）就必然无解。

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int b[] = {-1, 0, 1};
int n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sort(a + 1, a + n + 1);
    a[0] = -2;
    for(int i = 1; i <= n; i ++)
    {
        bool flag = false;
        for(int j = 0; j < 3; j ++)
        {
            if(a[i] + b[j] > a[i - 1])
            {
                a[i] += b[j];
                flag = true;
                break;
            }
        }
        if(!flag)
        {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}

相似题目

• LeetCode 945 Minimum Increment to Make Array Unique：通过 +1 操作使数组元素唯一，与本題思路同源（本题放宽到 ±1）。
• 拓展：允许每个元素在 $\{x-k,\dots,x+k\}$ 内调整的去重/构造类题，可训练贪心边界分析。

---

No.2 · 353三元组

点击展开题目

给定长度为 $n$ 的数组 $a$，统计满足以下条件的三元组 $(i, j, k)$ 的数量：

1. $0\le i<j<k<n$；
2. $a_i=3,\ a_j=5,\ a_k=3$。

• 输入：首行 $n$，次行 $n$ 个整数 $a_i$（$1\le a_i\le 10^5$）。
• 输出：一个整数，表示满足条件的三元组总数。

样例 1

输入：
5
3 5 3 5 3
输出：
4

解释：$(0,1,2)$、$(0,1,4)$、$(0,3,4)$、$(2,3,4)$，共 $4$ 种。

样例 2

输入：
3
3 5 3
输出：
1

解释：唯一三元组 $(0,1,2)$。

思路

核心思路：固定中间的 5，左右 3 的个数相乘，即为以它为中心的三元组数。

目标模式是 3 5 3，中间那个数必须是 $5$。对于任意一个值为 $5$ 的位置 $j$，只要数出它左边有多少个 $3$、右边有多少个 $3$，那么以这个 $5$ 作为中间元素能凑出的合法三元组数，就等于「左侧 3 的个数 × 右侧 3 的个数」——左侧任取一个 3 作 $i$、右侧任取一个 3 作 $k$，配合中间固定的 $5$，自然满足 $i<j<k$。

两步扫描实现：

1. 第一次遍历：统计整个数组中 $3$ 的总数，记为 totalThree。
2. 第二次遍历（从左到右）：用 leftThree 记录「当前位置左侧已经出现过的 3 的个数」。当扫到某个 $a_i=5$ 时：
   • 它左侧的 $3$ 有 leftThree 个；
   • 它右侧的 $3$ 有 totalThree - leftThree 个（当前这个 $5$ 本身不是 $3$，不计入，恰好对应"右侧"的定义）。
   • 于是以当前这个 $5$ 为中间元素的三元组数为 leftThree * (totalThree - leftThree)，累加到 sum。
3. 遍历结束，sum 即答案。

为什么正确且高效：枚举每一个 $5$ 作为中心，左右 3 的数量独立相乘，恰好不重不漏地覆盖所有 3 5 3 组合。时间复杂度 $O(n)$，空间复杂度 $O(1)$。

注意溢出：三元组总数可能很大（最坏约 $n^3$ 量级，$n=10^5$ 时可达 $10^{14}$ 级别），因此答案与计数变量都要用 long long，代码已用 LL 处理。

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], n;
LL totalThree;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
        totalThree += (a[i] == 3);
    }
    LL sum = 0, leftThree = 0;
    for(int i = 0; i < n; i ++)
    {
        if(a[i] == 3) leftThree ++;
        if(a[i] == 5)  sum += leftThree * (totalThree - leftThree);
    }
    cout << sum << endl;
    return 0;
}

相似题目

• LeetCode 930 Binary Subarrays With Sum：用「前缀和之差」统计满足和条件的区间，与本題"左右计数相乘"同属前缀统计技巧。
• LeetCode 1358 Number of Substrings Containing All Three Characters：固定模式/三元素的计数类题，思路可迁移。
• 拓展：固定"X Y X"型（中心对称）模式的计数，统一用「左计数 × 右计数」处理。

---

No.1 · 减半平衡调整

点击展开题目

给定长度为 $n$ 的整数数组 $a$，满足数组元素之和为 $0$。请构造长度为 $n$ 的整数数组 $b$，使得：

1. 对每个 $i$，$b_i=\lfloor a_i/2\rfloor$ 或 $b_i=\lceil a_i/2\rceil$；
2. 元素之和依然为 $0$。

若有多解，输出字典序最小的解（优先让靠前的数尽可能小，相同再比较下一个）。

数据范围：$2\le n\le 10^5$，$-10^5\le a_i\le 10^5$；保证 $\sum a_i=0$ 且一定有解。

• 输入：首行 $n$，次行 $n$ 个整数 $a_i$。
• 输出：一行 $n$ 个整数（空格分隔，行末无空格）。

样例 1

输入：
3
5 -3 -2
输出：
2 -1 -1

解释：$b=[\lfloor5/2\rfloor,\ \lceil-3/2\rceil,\ \lfloor-2/2\rfloor]=[2,-1,-1]$，和为 $0$ 且字典序最小。

样例 2

输入：
4
3 3 -3 -3
输出：
1 1 -1 -1

解释：$b=[\lfloor3/2\rfloor,\ \lfloor3/2\rfloor,\ \lceil-3/2\rceil,\ \lceil-3/2\rceil]=[1,1,-1,-1]$。

思路

核心思路：贪心构造 + 字典序最小化。

对原数组 $a$ 中每个元素，合法的 $b_i$ 只有两个候选值——向下取整 $\lfloor a_i/2\rfloor$ 与向上取整 $\lceil a_i/2\rceil$；当 $a_i$ 为偶数时两者相等。为了最终字典序最小，我们遵循一个原则：能取小就取小。

第一步（尽量取小）

先让每个 $b_i$ 都取较小值 $\lfloor a_i/2\rfloor$（代码中对正数即 a[i]/2 下取整，对负奇数额外 -- 修正，二者效果一致）。这样得到的数组和自然不会超过 $0$，记其与 $0$ 的差额为 $\text{need}=-\sum b_i\ (\ge 0)$。

第二步（从后往前补差额）

要让整体字典序最小，靠前位置的数绝不轻易增大，因此把"放大"操作尽量往后放。从数组末尾向前扫描，遇到某个 $a_i$ 是奇数（说明它还有"向上取整"这一更大的备选值）时，就把对应的 $b_i$ 加 $1$，并将 $\text{need}$ 减 $1$；一旦 $\text{need}$ 降为 $0$ 立刻停止。

为什么一定补得完、且首位永不需要动？因为 $\sum b_i$ 的"亏空"恰好等于所有奇数的个数的一半，而可用奇数位（不含下标 $0$）比所需数量更多，所以从后往前补一定能补满，无需触碰第一个元素。这也保证了字典序最小：任何让较靠前位置变大的方案，其字典序都大于本方案。

复杂度：$O(n)$ 时间与 $O(n)$ 空间，满足 $n\le 10^5$ 的数据规模。

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N];
LL sum;
int n;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
        b[i] = a[i] / 2;
        if(a[i] < 0 && a[i] % 2 != 0) b[i] --;
        sum += b[i];
    }
    int need = (int)(- sum);
    for(int i = n - 1; i > 0 && need > 0; i --)
    {
        if(a[i] % 2 != 0)
        {
            b[i] ++;
            need --;
        }
    }
    for(int i = 0; i < n; i ++)
        cout << b[i] << " \n"[i == n - 1];

    return 0;
}

相似题目

• LeetCode 945 类构造贪心：每个元素在多个候选值中二选一、再满足全局约束并求字典序最小，思路可迁移。
• AtCoder Beginner Contest 构造/贪心题：大量"每个元素二选一 + 字典序最小"的构造场景，建议作为同类训练。
• 拓展：Lexicographically smallest after operations 系列，强化"前不动、后补差"的贪心直觉。

贡献者: Withnoidea

下一页PowerShell 启动慢？6 秒优化到 0.6 秒的排查实录