小团是美团外卖的区域配送负责人,众所周知,外卖小哥一般都会同时配送若干单,小团在接单时希望把同一个小区的单子放在一起,然后由一名骑手统一配送。但是由于订单是叠在一起的,所以,他归类订单时只能知道新订单和已有的某个订单的小区是相同的,他觉得这样太麻烦了,所以希望你帮他写一个程序解决这个问题。 即给出若干个形如a b的关系,表示a号订单和b号订单是同一个小区的 ,请你把同一个小区的订单按照编号顺序排序,并分行输出,优先输出最小的订单编号较小的小区订单集合。订单的编号是1到n。(可能存在同时出现a b和b a这样的关系,也有可能出现a a这样的关系)
输入第一行是两个正整数n,m,表示接受的订单数量和已知的关系数量。(1<=n,m<=10000) 接下来有m行,每行两个正整数a和b,表示a号订单和b号订单属于同一个小区(1<=a,b<=n);
输出第一行包含一个整数x,表示这些订单共来自x个不同的小区。 接下来的输出包含x行,每行表示输出若干个订单编号,表示这些订单属于同一个小区,按照订单编号升序输出。优先输出最小的订单编号较小的小区。
5 5 1 2 2 2 3 1 4 2 5 4
1 1 2 3 4 5
考点:排序
数据规模 m ≤ 1e4 | 限制 1 秒 / 256MB | 标准输入输出
参考方向:排序
先用 O(n log n) 排序把无序变有序,后续处理往往就简单了。
思路框架(排序 通法 · 非本题专属)
实现要点:在 C++ 中用 std::sort,Python 用 sorted();注意自定义比较函数的严格弱序。
复杂度:时间 O(n log n) | 空间 O(log n) ~ O(n)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1
5 5 / 1 2 / 2 2 / 3 1 / 4 2 / 5 41 / 1 2 3 4 5解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:美团2023校招技术第2场编程题。