GESP 题解库 / 7 级题解 / [GESP202503 七级] 图上移动 · 第 10 / 24 题
GESP202503 七级 · P11964 · 简单

图上移动

从每个结点出发,恰好走 j 步(j = 1 … k)能到达多少个不同的结点。

📊
n, m ≤ 500,k ≤ 20
数据规模
🔢
n 行 × k 列
输出规模
⚡
O(n · k · (n + m))
时间复杂度
🎯
逐层扩展"恰好 j 步可达集合"
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给一张包含 n 个结点、m 条边的无向图,结点编号 1 … n。小 A 从某个结点出发,每一步移动到与当前结点相邻的结点。

对每个结点 i(1 ≤ i ≤ n),求:从 i 出发恰好移动 1, 2, …, k 步后,小 A 可能位于的结点数量。输出共 n 行,第 i 行有 k 个整数,第 j 个数表示"恰好 j 步"的答案。

💡
人话翻译:对每个起点维护一个"恰好 j 步能站上去的点"的集合。
初始(0 步)集合只有起点自己;每走一步,就把集合里所有点的邻居全部并进来,再数一数集合里有几个点,就是这一层的答案。
关键字是"恰好"——每一步都必须真的沿一条边走,不许"原地不动"(除非该点有自环)。
n ≤ 500、k ≤ 20 很小,所以直接对每个起点做 k 轮集合扩展,总运算量约 5 × 10⁶,非常安全。

🔍 关键词提取

恰好 j 步可达集合扩展布尔数组去重重边与自环

已知条件

项目说明
输入第一行 n, m, k;随后 m 行每行两个正整数 uᵢ, vᵢ
输出n 行,第 i 行 k 个整数(空格分隔)
数据范围1 ≤ n ≤ 500,1 ≤ m ≤ 500,1 ≤ k ≤ 20
图的性质无向图,可能出现重边甚至自环
移动规则每步必须走一条边;结点与边都可以重复经过

需要解决的问题

02
思维导图
整理解题思路的全貌
👟 逐层扩展"恰好 j 步可达集合"
🧠 状态定义
cur[v]:恰好 j 步能否站在 v
初始 cur 只有起点 i 为真
只记录"能否",不记录距离
答案 = cur 中真值个数
🔁 扩展规则
nxt 全清空
枚举所有 cur[v] = 真的 v
把 v 的所有邻居在 nxt 中置真
cur ← nxt 进入下一层
🧮 复杂度账本
每个起点做 k 轮
每轮扫 n 个点 + 所有邻接边
单起点 O(k(n + m))
总计 O(n · k · (n + m)) ≈ 5 × 10⁶
⚠️ 易错点
把"恰好"做成"至多"
每层忘记清空 nxt
孤立点没输出 0
漏掉自环带来的"停留"
03
样例手算推导
样例的完整推演

🧮 样例 1:n = 4, m = 4, k = 3(边 1-2, 1-3, 2-3, 3-4)

先把邻接表写出来:1 → {2, 3},2 → {1, 3},3 → {1, 2, 4},4 → {3}。然后从起点 1 出发,一层一层看集合怎么长。

步数 j上一层集合 cur各点的邻居并起来本层集合 nxt数量
1{1}1 → {2, 3}{2, 3}2
2{2, 3}2 → {1, 3};3 → {1, 2, 4}{1, 2, 3, 4}4
3{1, 2, 3, 4}1 → {2, 3};2 → {1, 3};3 → {1, 2, 4};4 → {3}{1, 2, 3, 4}4

起点 1 的答案:2 4 4 ✓

📊 四个起点的完整结果

起点j = 1j = 2j = 3该行输出
1{2, 3} → 2{1, 2, 3, 4} → 4{1, 2, 3, 4} → 42 4 4
2{1, 3} → 2{1, 2, 3, 4} → 4{1, 2, 3, 4} → 42 4 4
3{1, 2, 4} → 3{1, 2, 3} → 3{1, 2, 3, 4} → 43 3 4
4{3} → 1{1, 2, 4} → 3{1, 2, 3} → 31 3 3
1
起点 3 为什么第 2 步只有 3 个?

cur = {1, 2, 4}

1 的邻居 {2, 3},2 的邻居 {1, 3},4 的邻居 {3}

并起来 = {1, 2, 3},只有 3 个

因为 4 号点没有自环,不能"原地停一步"

✅ 3 3 4

2
起点 4 第 1 步只有 1 个

4 只连 3,所以恰好 1 步只能站到 3

第 2 步从 3 出发 → {1, 2, 4}

第 3 步从 {1, 2, 4} 出发 → {2, 3} ∪ {1, 3} ∪ {3} = {1, 2, 3}

✅ 1 3 3

🔑
看清楚"集合在滚动"这件事:每层的输入是上一层的整个集合,不是"最近一步走过的点"。
所以起点 1 在第 3 步仍然是 4 个点——因为 {1, 2, 3, 4} 里每个点都能走到别的点,集合已经稳定,不会再缩水。

🧮 反例:把"恰好"当成"至多"就会错

只看一条边 1-2,k = 3。"恰好"必须每步都走,于是只能在 1、2 之间来回跳。

j恰好 j 步可达数量至多 j 步可达数量
1{2}1{2}1
2{1}1{1, 2}2
3{2}1{1, 2}2
⚠️
两个世界:用一次 BFS 求最短路、再数"距离 ≤ j"的结点数,得到的是"至多 j 步"的答案(上表右边那两列),在 j = 2, 3 时全都偏大。
本题要的是"恰好 j 步",所以必须老老实实逐层扩展集合,不能偷换成最短路。
只有当图里存在自环、(或存在"能改变奇偶性的奇环")时,两者才可能巧合一致——不能赌这一点。
04
解法对比
逐层集合扩展 vs 按起点 BFS 分层

⚔️ 解法对比

🟢 逐层集合扩展(推荐) 推荐

对每个起点维护"恰好 j 步可达"的布尔集合,逐层做邻居并集

  • 时间 O(n · k · (n + m))
  • 约 5 × 10⁶ 次操作
  • 两个布尔数组即可,代码约 25 行
  • 重边/自环天然处理正确
💡
为什么这么省心:把集合表示成布尔数组后,"并集"就是不断地置真,"去重"是自动完成的;数答案时只要遍历一遍数组统计真值个数。重边不会让计数变多,这正是布尔数组的好处。

🟠 按起点 BFS 求最短路

一次 BFS 得到最短距离,认为"距离 ≤ j 即可达"

  • 时间 O(n(n + m))
  • 代码更短(约 15 行)
  • 语义是"至多 j 步"
  • 本题会 WA
⚠️
只差一个字,答案全错:"至多"允许你少走或原地不动,"恰好"强制每步都走。做题时把题目里的"恰好/至多/至少"圈出来,这是最容易被忽略而失分的地方。

📈 性能对比

方案复杂度代码量
逐层集合扩展O(n · k · (n + m)) ≈ 5 × 10⁶约 25 行
按起点 BFS 分层O(n(n + m)),语义不符❌ 答案错误
邻接矩阵快速幂O(n³ log k)约 40 行,杀鸡用牛刀
05
算法流程图
从一个起点逐层扩展集合
开始读入 n, m, k 与所有边,建立邻接表取下一个起点 i:cur 中只把 cur[i] 置真j 从 1 遍历到 knxt 全清空对每个 cur[v] = 真的 v,把 v 的所有邻居在 nxt 中置真输出 nxt 中真值个数作为答案,并令 cur ← nxt还有起点没处理吗?还有 ✓回到"取下一个起点",重新初始化 cur都处理完了 ✗结束,n 行答案已输出结束j 加 1 继续扩展
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

👟 恰好 j 步可达结点数

第一行输入 n m k,随后 m 行输入一条边。程序对每个起点逐层扩展集合并给出完整答案,同时给出"至多 j 步"作对照。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(逐层集合扩展)

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<int> g[505];
bool cur[505], nxt[505];

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);            // 无向边存两次;重边不影响布尔标记
    }

    for (int s = 1; s <= n; s++) {
        for (int v = 1; v <= n; v++) cur[v] = false;
        cur[s] = true;                // 恰好 0 步:只能待在起点

        for (int j = 1; j <= k; j++) {
            for (int v = 1; v <= n; v++) nxt[v] = false;    // 每层必须清空

            for (int v = 1; v <= n; v++) {
                if (!cur[v]) continue;                     // 没站在 v 上就跳过
                for (int w : g[v]) nxt[w] = true;          // 邻居并入(自动去重)
            }

            int cnt = 0;
            for (int v = 1; v <= n; v++) if (nxt[v]) cnt++;

            if (j > 1) putchar(' ');
            printf("%d", cnt);

            for (int v = 1; v <= n; v++) cur[v] = nxt[v];  // 滚动到下一层
        }
        printf("\n");
    }
    return 0;
}
🔑
为什么 cur[s] = true 就代表"恰好 0 步"?因为 0 步时你必然站在起点上,别的点一个都到不了。
接着第 1 轮把"起点的所有邻居"标记进 nxt,正好对应"恰好 1 步";第 2 轮再把"这些点的邻居"并起来,对应"恰好 2 步"……层层递推,每一轮都是"再走一条边"。

📖 关键几行怎么看

代码作用为什么这样写
cur[s] = true;初始状态恰好 0 步只能待在起点 s
nxt[v] = false;每层清空nxt 是"新一层"的集合,必须从空开始
for (int w : g[v]) nxt[w] = true;集合扩展邻居并入 nxt;布尔数组自动去重,重边无影响
cur[v] = nxt[v];滚动前进本层结果成为下一层的输入
⚠️
四个坑:① 把"恰好"做成"至多"(例如不强制每步都走、或直接用最短路);② 每层忘记清空 nxt(结果会越滚越大);③ 忘记把 nxt 拷回 cur(一直停在第 1 层);④ 用"标记次数"代替布尔数组(同一邻居被多个点标记会重复计数)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4 4 3
1 2
1 3
2 3
3 4
2 4 4
2 4 4
3 3 4
1 3 3
题面样例
2 1 2
1 2
1 1
1 1
一条边:两步后必须原路返回自己
2 1 1
1 2
1
1
k = 1,只看一步
3 1 3
1 2
1 1 1
1 1 1
0 0 0
结点 3 孤立,任何步数都是 0
2 2 2
1 1
1 2
2 2
1 2
自环让"原地停留"也算一步
3 3 4
1 2
1 3
2 3
2 3 3 3
2 3 3 3
2 3 3 3
完全图:两步后处处可达
✅
自查清单:① 集合是"恰好 j 步"推出来的吗?② 每层清空 nxt 并把 nxt 拷回 cur 吗?③ 度为 0 的点输出 0 吗?

🚨 易错点清单

⚠️
把"恰好"读成"至多":本题每步都必须走一条边,用最短路分层会得到偏大的答案。
⚠️
每层忘记清空 nxt:旧标记会残留,数量只增不减。
⚠️
孤立点没输出 0:度为 0 的结点从第 1 步起就没有可达点。
⚠️
自环/重边处理错:自环让"停留"合法;重边不能让计数变多,必须用布尔数组去重。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n · k · (n + m))
空间复杂度
O(n + m)
n 最大
500
总运算量
约 5 × 10⁶

时间怎么算的?

空间都用在哪?

邻接表 O(n + m),外加两个长度 n + 1 的布尔数组。

✅ 约 500 万次操作,1 秒限制下轻松通过。关键是"用集合合并代替了搜索",避免了任何指数级枚举。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// "恰好 j 步可达集合" 通用模板
bool cur[N], nxt[N];
cur[s] = true;                       // 恰好 0 步
for (int j = 1; j <= k; j++) {
    memset(nxt, 0, sizeof(nxt));
    for (int v = 1; v <= n; v++)
        if (cur[v]) for (int w : g[v]) nxt[w] = true;   // 并集 = 置真
    ans[j] = 集合 nxt 中真值的个数;
    memcpy(cur, nxt, sizeof(cur));
}

// 只问"能不能到"(至多 j 步):一次 BFS 求 dist,判 dist <= j
// 问"恰好 j 步的方案数":DP 计数 dp[j][v] = Σ dp[j-1][u],n 大时用矩阵快速幂
// 把并集换成异或:变成"模 2 意义下的可达性"
// 有自环 ⟹ 可以原地等待 ⟹ 奇偶性不再是障碍

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
布尔集合扩展cur → nxt 逐层推进可达性、染色、状态集合类问题
布尔数组去重重边不重复计数任何需要"去重统计"的场景
恰好 vs 至多每步都必须走一条边最短路与"恰好步数"的区分
分层迭代k 层外循环 + 集合内循环BFS 分层、时间步模拟、细胞自动机
🌟
思考题:如果 k 变成 10¹⁸,这题怎么办?(提示:集合的演化是确定性的——cur 只由上一个 cur 决定,而可能的集合个数有限,所以序列迟早会开始周期性重复。只要记录"每个集合第一次出现的位置",一旦发现重复就求出周期,把剩下的步数按周期跳过去即可。这就是"找循环节"的通用套路。)