京东 · 图 · 算法编程题
京东 图 n ≤ 1e3 时限 1 秒 / 256 MB

题目描述

牛之国有 n 个城市，牛牛作为牛之国国王，他希望所有牛之国的城市能够连通起来。现在他下令牛之国的所有施工队同时施工，同时已知牛之国的施工队的施工速度均为1距离单位/年，对于每个城市，城市的领导者都会向每个相邻的城市派出施工队进行修路（所有城市相邻），并且每个施工队都按照最短的路线修路，如果两个施工队碰头，那么两个城市相连。
现在给你 n 个城市的坐标，牛牛想知道牛之国的城市最少需要多少年才能全部连通(城市A和城市B连通，当且仅当A到B有一条通路)。

输入输出

输入描述
第一行一个整数 n ( 1 ≤ n ≤ 1000 )，表示城市数量。
接下来 n 行每行两个整数 x_i (-10^8 ≤ x_i ≤ 10^8) , y_i (-10^8 ≤ y_i ≤ 10^8) 用空格分隔，表示城市的坐标。
输出描述
输出仅有一个整数，表示城市相连需要的年数向上取整的结果。
例如，如果需要2.5年可以连通，请输出 3，如果如要 4 年可以连通，请输出 4。

样例共 2 组

样例 1 · 当(6,0)和(0,0)连在一起时，所有城市连在一起，此时需要3年。
输入
3
0 0
0 5
6 0
输出
3
样例 2 · 初始不连通，0.5年可以连通，向上取整得到 1。
输入
2
0 0
1 0
输出
1

算法解析依据充分

考点：图 · 计算几何

数据规模 n ≤ 1e3 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e3
  • 元素值域：x_i ≤ 100000000，y_i ≤ 100000000（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：图

把关系抽象成点与边，再按问的类型选遍历/最短路/连通性算法。

思路框架（图 通法 · 非本题专属）

  1. 建图：邻接表（稀疏）或邻接矩阵（稠密）。
  2. 问「最少几步 / 最短路径」且边权为 1 → BFS。
  3. 问「是否连通 / 需要加几条边连通」→ 并查集 / 连通块计数。
  4. 问「带权最短路」→ Dijkstra（非负权）或 Floyd（点数小、多源）。
  5. 问「依赖顺序」→ 拓扑排序。

实现要点：注意是有向图还是无向图，无向图加边记得双向。

复杂度：时间 O(V+E) 遍历 / O(E log V) Dijkstra ｜ 空间 O(V+E)

该范式的通法易错点

  • 无向图只加了单向边。
  • BFS 入队时没标记访问，导致重复入队。

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 100000000 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 / 0 0 / 0 5 / 6 0 → 输出 3

当(6,0)和(0,0)连在一起时，所有城市连在一起，此时需要3年。

样例 2：输入 2 / 0 0 / 1 0 → 输出 1

初始不连通，0.5年可以连通，向上取整得到 1。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2024年秋招-京东-后端开发岗-第2批笔试；2024年秋招-京东-算法岗-第2批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解