【蓝桥杯】0仙境诅咒 — BFS/DFS 图论连通性问题C 题解1. 题目描述题目来源蓝桥云课 - 0仙境诅咒难度易 (LV.1)标签DFS / BFS / 图的连通性问题简述在仙境中有 N 位修仙者坐标分别为 (X_i, Y_i)。第一位修仙者妮妮即下标为 0 的修仙者受到了诅咒。诅咒具有传递性如果一个修仙者被诅咒那么距离他不超过 D 的范围内的所有修仙者也都会被诅咒。请求出最终哪些修仙者会被诅咒。数据范围1 N 1000-1000 X_i, Y_i 1000坐标为实数1 D 10002. 常见误区与原代码分析很多初学者容易将题目理解为“只计算每个人到原点 (0,0) 或妮妮的距离”。典型错误思路仅判断每个修仙者到妮妮的距离是否 D。忽略了连通性连锁传播即便修仙者 C 距离妮妮超过 D但只要 C 距离“已被诅咒的修仙者 B”不超过 DC 就会被感染。3. 解题思路本题本质上是一个无向图的连通块遍历问题建立连通关系两点 u 和 v 之间的欧氏距离小于等于 D即 (X_u - X_v)^2 (Y_u - Y_v)^2 D^2时两点之间存在一条无向边。图的遍历从起点 0妮妮开始使用BFS广度优先搜索或DFS深度优先搜索遍历所有可达的点。精度处理坐标为实数计算距离平方时用double存储比较时可加上微小的浮点误差容限如1e-9。由于 N 1000整体判断的复杂度为 O(N^2)可以完美在 2 秒内通过。4. C AC 代码#includebits/stdc.husingnamespacestd;// 计算两点之间的欧氏距离平方doubledistSq(doublex1,doubley1,doublex2,doubley2){return(x1-x2)*(x1-x2)(y1-y2)*(y1-y2);}intmain(){// 优化输入输出效率ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cinn))return0;vectorpairdouble,doublep(n);for(inti0;in;i){cinp[i].firstp[i].second;}doubled;cind;doubled2d*d;// 距离阈值的平方vectorboolvis(n,false);queueintq;// 起点第 0 位修仙者妮妮首先被诅咒vis[0]true;q.push(0);// BFS 遍历while(!q.empty()){intuq.front();q.pop();for(intv0;vn;v){if(!vis[v]){// 判断 u 与 v 之间的距离平方是否 D^2if(distSq(p[u].first,p[u].second,p[v].first,p[v].second)d21e-9){vis[v]true;q.push(v);}}}}// 顺序输出结果for(inti0;in;i){cout(vis[i]?1:0)\n;}return0;}5. 复杂度分析时间复杂度O(N2)\mathcal{O}(N^2)O(N2)每个节点入队一次遍历每个节点时扫描其余NNN个节点对N≤1000N \le 1000N≤1000而言计算量约为10610^6106次轻松在 2 秒限制内跑完。空间复杂度O(N)\mathcal{O}(N)O(N)仅需存储NNN个点的坐标数组、访问标记数组vis及 BFS 队列。
【蓝桥杯】0仙境诅咒 — BFS/DFS 图论连通性问题（C++ 题解）
【蓝桥杯】0仙境诅咒 — BFS/DFS 图论连通性问题C 题解1. 题目描述题目来源蓝桥云课 - 0仙境诅咒难度易 (LV.1)标签DFS / BFS / 图的连通性问题简述在仙境中有 N 位修仙者坐标分别为 (X_i, Y_i)。第一位修仙者妮妮即下标为 0 的修仙者受到了诅咒。诅咒具有传递性如果一个修仙者被诅咒那么距离他不超过 D 的范围内的所有修仙者也都会被诅咒。请求出最终哪些修仙者会被诅咒。数据范围1 N 1000-1000 X_i, Y_i 1000坐标为实数1 D 10002. 常见误区与原代码分析很多初学者容易将题目理解为“只计算每个人到原点 (0,0) 或妮妮的距离”。典型错误思路仅判断每个修仙者到妮妮的距离是否 D。忽略了连通性连锁传播即便修仙者 C 距离妮妮超过 D但只要 C 距离“已被诅咒的修仙者 B”不超过 DC 就会被感染。3. 解题思路本题本质上是一个无向图的连通块遍历问题建立连通关系两点 u 和 v 之间的欧氏距离小于等于 D即 (X_u - X_v)^2 (Y_u - Y_v)^2 D^2时两点之间存在一条无向边。图的遍历从起点 0妮妮开始使用BFS广度优先搜索或DFS深度优先搜索遍历所有可达的点。精度处理坐标为实数计算距离平方时用double存储比较时可加上微小的浮点误差容限如1e-9。由于 N 1000整体判断的复杂度为 O(N^2)可以完美在 2 秒内通过。4. C AC 代码#includebits/stdc.husingnamespacestd;// 计算两点之间的欧氏距离平方doubledistSq(doublex1,doubley1,doublex2,doubley2){return(x1-x2)*(x1-x2)(y1-y2)*(y1-y2);}intmain(){// 优化输入输出效率ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cinn))return0;vectorpairdouble,doublep(n);for(inti0;in;i){cinp[i].firstp[i].second;}doubled;cind;doubled2d*d;// 距离阈值的平方vectorboolvis(n,false);queueintq;// 起点第 0 位修仙者妮妮首先被诅咒vis[0]true;q.push(0);// BFS 遍历while(!q.empty()){intuq.front();q.pop();for(intv0;vn;v){if(!vis[v]){// 判断 u 与 v 之间的距离平方是否 D^2if(distSq(p[u].first,p[u].second,p[v].first,p[v].second)d21e-9){vis[v]true;q.push(v);}}}}// 顺序输出结果for(inti0;in;i){cout(vis[i]?1:0)\n;}return0;}5. 复杂度分析时间复杂度O(N2)\mathcal{O}(N^2)O(N2)每个节点入队一次遍历每个节点时扫描其余NNN个节点对N≤1000N \le 1000N≤1000而言计算量约为10610^6106次轻松在 2 秒限制内跑完。空间复杂度O(N)\mathcal{O}(N)O(N)仅需存储NNN个点的坐标数组、访问标记数组vis及 BFS 队列。
