C++ BFS short clean solution with explanation


  • 32
    D
    class Solution {
     public:
      vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        // Initialize the undirected graph
        vector<unordered_set<int>> adj(n);
        for (pair<int, int> p : edges) {
          adj[p.first].insert(p.second);
          adj[p.second].insert(p.first);
        }
        // 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) {
          if (adj[i].size() == 1) {
            current.push_back(i);
          }
        }
        // BFS the graph
        while (true) {
          vector<int> next;
          for (int node : current) {
            for (int neighbor : adj[node]) {
              adj[neighbor].erase(node);
              if (adj[neighbor].size() == 1) next.push_back(neighbor);
            }
          }
          if (next.empty()) return current;
          current = next;
        }
      }
    };

  • 0
    H

    This solution is clear and easy to understand


  • 1
    S

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


  • 2
    P

    Where is the explanation ? I only see the code .


  • 0
    S

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


  • 0
    B

    Maybe setting 'current' as a set is better?


  • 0
    M

    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.


  • 0
    J

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


Log in to reply
 

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