应用直觉电面，没见过的题

给一堆有坐标的点，要求你把它们

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

求米！！加米不扣分的

这题地里应该出现过了。。用union find和dfs都能写
dfs的话 大概就是先建立一个图 按照1cm的dist来建立
然后dfs找connected components

比如0和1距离是1，1和2距离也是1，但是0和2距离大于1，那么012是一组么，即有没有传递性，union find并不能解决两俩都小于d

匿名用户 发表于 2025-3-20 02:07
比如0和1距离是1，1和2距离也是1，但是0和2距离大于1，那么012是一组么，即有没有传递性，union find并不能 ...

诶 是这样吗？我以为，如果0,1能及时并成一个cluster的话，012就可。
所以也取决于scan时候的顺序？需要先sort input，不然会miss一些点？

dfs感覺會TLE? union find才是optimal solution的感覺?