从每个结点出发,恰好走 j 步(j = 1 … k)能到达多少个不同的结点。
给一张包含 n 个结点、m 条边的无向图,结点编号 1 … n。小 A 从某个结点出发,每一步移动到与当前结点相邻的结点。
对每个结点 i(1 ≤ i ≤ n),求:从 i 出发恰好移动 1, 2, …, k 步后,小 A 可能位于的结点数量。输出共 n 行,第 i 行有 k 个整数,第 j 个数表示"恰好 j 步"的答案。
恰好 j 步可达集合扩展布尔数组去重重边与自环
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n, m, k;随后 m 行每行两个正整数 uᵢ, vᵢ |
| 输出 | n 行,第 i 行 k 个整数(空格分隔) |
| 数据范围 | 1 ≤ n ≤ 500,1 ≤ m ≤ 500,1 ≤ k ≤ 20 |
| 图的性质 | 无向图,可能出现重边甚至自环 |
| 移动规则 | 每步必须走一条边;结点与边都可以重复经过 |
先把邻接表写出来: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 = 1 | j = 2 | j = 3 | 该行输出 |
|---|---|---|---|---|
| 1 | {2, 3} → 2 | {1, 2, 3, 4} → 4 | {1, 2, 3, 4} → 4 | 2 4 4 |
| 2 | {1, 3} → 2 | {1, 2, 3, 4} → 4 | {1, 2, 3, 4} → 4 | 2 4 4 |
| 3 | {1, 2, 4} → 3 | {1, 2, 3} → 3 | {1, 2, 3, 4} → 4 | 3 3 4 |
| 4 | {3} → 1 | {1, 2, 4} → 3 | {1, 2, 3} → 3 | 1 3 3 |
cur = {1, 2, 4}
1 的邻居 {2, 3},2 的邻居 {1, 3},4 的邻居 {3}
并起来 = {1, 2, 3},只有 3 个
因为 4 号点没有自环,不能"原地停一步"
✅ 3 3 4
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-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 |
对每个起点维护"恰好 j 步可达"的布尔集合,逐层做邻居并集
一次 BFS 得到最短距离,认为"距离 ≤ j 即可达"
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 逐层集合扩展 | O(n · k · (n + m)) ≈ 5 × 10⁶ | 约 25 行 |
| 按起点 BFS 分层 | O(n(n + m)),语义不符 | ❌ 答案错误 |
| 邻接矩阵快速幂 | O(n³ log k) | 约 40 行,杀鸡用牛刀 |
第一行输入 n m k,随后 m 行输入一条边。程序对每个起点逐层扩展集合并给出完整答案,同时给出"至多 j 步"作对照。
点按钮开始 →
#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 步时你必然站在起点上,别的点一个都到不了。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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 层);④ 用"标记次数"代替布尔数组(同一邻居被多个点标记会重复计数)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 4 3 | 2 4 4 2 4 4 3 3 4 1 3 3 | 题面样例 |
2 1 2 | 1 1 1 1 | 一条边:两步后必须原路返回自己 |
2 1 1 | 1 1 | k = 1,只看一步 |
3 1 3 | 1 1 1 1 1 1 0 0 0 | 结点 3 孤立,任何步数都是 0 |
2 2 2 | 2 2 1 2 | 自环让"原地停留"也算一步 |
3 3 4 | 2 3 3 3 2 3 3 3 2 3 3 3 | 完全图:两步后处处可达 |
邻接表 O(n + m),外加两个长度 n + 1 的布尔数组。
✅ 约 500 万次操作,1 秒限制下轻松通过。关键是"用集合合并代替了搜索",避免了任何指数级枚举。
// "恰好 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 分层、时间步模拟、细胞自动机 |