参考了评论区的解法,画个解法示意图。
解题思路:
首先假设 "1" 的第一阶邻居的每个 "2,3,4" 属于不同的连通区域,并把每个连通区域赋予一个 id 来标识。
把连通区域的标识通过 bfs 扩散开来。扩散的过程中检查是否存在该情况:一个点能被不同的连通区域赋值。存在该情况说明它们其实是一个连通区域,即存在一个包含 "1" 节点的环
class Solution { public: string solve(vector<int>& param, vector<Point>& edge) { int n = param[0], m = param[1]; vector<vector<int>> next(n+1, vector<int>()); for(auto e:edge){ next[e.x].push_back(e.y); next[e.y].push_back(e.x); } vector<int> vis(n+1, 0); vis[1] = -1; vector<int> q, aux; int id = 1; for(auto e:next[1]){ q.push_back(e); vis[e] = id++; } while(q.size()){ for(auto e:q){ for(auto nxt:next[e]){ if(vis[nxt]==0){ // 没被访问过 vis[nxt] = vis[e]; aux.push_back(nxt); }else if(vis[nxt]!=-1){ // 被访问过,且不是 "1" 号节点 if(vis[e]!=vis[nxt]) return "Yes"; } } } q.clear(); swap(aux, q); } return "No"; } };