LeetCode 310. 最小高度树（图 聪明的BFS，从外向内包围）

示例 1:
输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3 

输出: [1]

示例 2:
输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

输出: [3, 4]

说明:
 根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 
 换句话说，一个任何没有简单环路的连通图都是一棵树。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

class Solution {
	unordered_map<int,unordered_set<int>> g;
	vector<int> vertex;
	queue<int> q;
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        for(auto& e : edges)
        {
        	g[e[0]].insert(e[1]);
        	g[e[1]].insert(e[0]);
        }
        bool visited[n];
        int minh = INT_MAX, h;
        for(int i = 0; i < n; i++)
        {
        	memset(visited, 0, sizeof(visited));
        	h = 0;
        	visited[i] = true;
        	q.push(i);
        	BFS(h,visited);
        	if(h < minh)
        	{
        		minh = h;
        		vertex.clear();
        		vertex.push_back(i);
        	}
        	else if(h == minh)
        		vertex.push_back(i);
        }
        return vertex;
    }

    void BFS(int& h, bool* visited)
    {
    	int tp, size;
    	while(!q.empty())
    	{
    		size = q.size();
    		while(size--)
    		{
	    		tp = q.front();
	    		q.pop();
	    		for(const int& id : g[tp])
	    		{
	    			if(!visited[id])
	    			{
	    				q.push(id);
	    				visited[id] = true;
	    			}
	    		}
	    	}
	    	h++;
    	}
    }
};

class Solution {
	unordered_map<int,unordered_set<int>> g;
	vector<int> vertex;
	queue<int> q;
    vector<int> lastLv;
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        for(auto& e : edges)
        {
        	g[e[0]].insert(e[1]);
        	g[e[1]].insert(e[0]);
        }
        bool visited[n];
        bool outSide[n];//是最外围的节点？是最外围的，不用从他开始BFS，高度肯定不是最小的
        memset(outSide, 0, sizeof(outSide));
        int minh = INT_MAX, h = 0;
        for(int i = 0; i < n; i++)
        {
            if(minh > 2 && outSide[i])
                continue;
        	memset(visited, 0, sizeof(visited));
        	h = 0;
        	visited[i] = true;
        	q.push(i);
        	BFS(h,visited,outSide);
        	if(h < minh)
        	{
        		minh = h;
        		vertex.clear();
        		vertex.push_back(i);
        	}
        	else if(h == minh)
        		vertex.push_back(i);
        }
        return vertex;
    }

    void BFS(int& h, bool* visited, bool* outSide)
    {
    	int tp, size;
    	while(!q.empty())
    	{
    		size = q.size();
            lastLv.clear();
    		while(size--)
    		{
	    		tp = q.front();
	    		q.pop();
	    		for(const int& id : g[tp])
	    		{
	    			if(!visited[id])
	    			{
	    				q.push(id);
	    				visited[id] = true;
                        lastLv.push_back(id);
	    			}
	    		}
	    	}
	    	h++;
    	}
        for(auto id : lastLv)
            outSide[id] = true;
    }
};

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1)
            return {0};
        int i, tp, size;
        unordered_map<int,unordered_set<int>> g;//图的邻接表
        vector<int> vertex;
        queue<int> q;//队列
        for(auto& e : edges)
        {
            g[e[0]].insert(e[1]);//
            g[e[1]].insert(e[0]);
        }
        for(i = 0; i < n; i++)
            if(g[i].size() == 1)//出入度1,最外层的节点
                q.push(i);//进入队列
        while(n > 2)//剩余节点大于2
        {
            size = q.size();//在队列里的节点，减去
            n -= size;//剩余的节点个数n
            while(size--)
            {
                tp = q.front();//待删除的节点
                q.pop();
                for(const int& id : g[tp])
                {
                    g[id].erase(tp);
                    if(g[id].size() == 1)//id变成最外层了
                        q.push(id);//进入队列，待删
                }
            }
        }

        while(!q.empty())
        {
            vertex.push_back(q.front());
            q.pop();
        }
        return vertex;
    }
};