京东笔试题------紧急疏散-----创建邻接表，广度优先遍历，

京东笔试题------紧急疏散-----创建邻接表，广度优先遍历，

/* 这道题是找根节点下的最大子树 因为是多叉树，可以利用图中的邻接表，这里利用vector和list实现 先记录根节点下的次子节点子节点。分别以次子节点为根，然后利用广度优先或者深度优先遍历计算得到各个节点的子树节点总和 取次子节点中最大的值作为结果*/#includeusing namespace std;int main(){ int m;cin >> m; vector> vec(m, vector()); int x,y; //创建邻接表 while(cin >>x >>y) { //建立邻接表，对应的两个节点的值都加进去 vec[x-1].push_back(y-1); vec[y-1].push_back(x-1); } queue que; //表示是否被访问过 vector vis(m, false); //根节点默认已经访问 vis[0] = true; int res = 0; //广度优先遍历 次子节点分别求子树节点个数， for(int i = 0; i < vec[0].size();i++) { que.push(vec[0][i]); int num = 0; while(!que.empty()) { int tem = que.front(); num++; vis[tem] = true; for(auto it = vec[tem].begin(); it != vec[tem].end(); it++) { if(!vis[*it]) { que.push(*it); } } que.pop(); } //取每个根节点的子节点的最大值，赋值给res,最后返回 res = res < num ? num : res; } cout << res << endl; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。