# C++ BFS short clean solution with explanation

• ``````class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
// Initialize the undirected graph
for (pair<int, int> p : edges) {
}
// Corner case
vector<int> current;
if (n == 1) {
current.push_back(0);
return current;
}
// Create first leaf layer
for (int i = 0; i < adj.size(); ++i) {
current.push_back(i);
}
}
// BFS the graph
while (true) {
vector<int> next;
for (int node : current) {
for (int neighbor : adj[node]) {
}
}
if (next.empty()) return current;
current = next;
}
}
};``````

• This solution is clear and easy to understand

• Why does it check if (adj[neighbor].size() == 1)? all node in current should have only one neighbor.

• Where is the explanation ? I only see the code .

• because not all neighbors of current node has only one neighbor.

• Maybe setting 'current' as a set is better?

• If the graph has cycles, this solution will fail. For example,
4
[[1,0],[1,2],[1,3],[2,0],[2,3]]

``````    2
/  |  \
3 - 1 - 0
``````

This solution cannot find leaves.

• @moto72 this is a tree graph, I think we don't need to consider the cycle condition

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.