经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
1004 Counting Leaves (30 分)(树的遍历)
来源:cnblogs  作者:陈臣12  时间:2018/12/10 9:46:48  对本文有异议

给出一棵树,问每一层各有多少叶子节点

 

dfs遍历树

  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. vector<int>p[150];
  5. int n,m;
  6. int node ,k;
  7. int vis[150];
  8. int maxn=-1;
  9. void dfs(int node,int step)
  10. {
  11. if(p[node].empty()){
  12. vis[step]++;
  13. maxn=max(step,maxn);
  14. }
  15. else{
  16. for(int i=0;i<p[node].size();i++){
  17. dfs(p[node][i],step+1);
  18. }
  19. }
  20. }
  21. int main()
  22. {
  23. ios::sync_with_stdio(false);
  24. cin>>n>>m;
  25. for(int i=0;i<m;i++){
  26. cin>>node>>k;
  27. int t;
  28. for(int j=0;j<k;j++){
  29. cin>>t;
  30. p[node].push_back(t);
  31. }
  32. }
  33. dfs(1,1);
  34. cout<<vis[1];
  35. for(int i=2;i<=maxn;i++){
  36. cout<<" "<<vis[i];
  37. }
  38. cout<<endl;
  39. return 0;
  40. }

 

bfs遍历求树

  1. 1 #include<bits/stdc++.h>
  2. 2
  3. 3 using namespace std;
  4. 4 struct NODE
  5. 5 {
  6. 6 int data;
  7. 7 int step;
  8. 8 NODE(){}
  9. 9 NODE(int data1,int step1):data(data1),step(step1){}
  10. 10 };
  11. 11 vector<int>p[150];
  12. 12 int n,m;
  13. 13 int node ,k;
  14. 14 int vis[150];
  15. 15 int maxn=-1;
  16. 16 void bfs(int node,int step)
  17. 17 {
  18. 18 queue<NODE>Q;
  19. 19 Q.push(NODE(node,step));
  20. 20 while(!Q.empty()){
  21. 21 NODE u=Q.front();
  22. 22 Q.pop();
  23. 23 if(p[u.data].empty()){
  24. 24 maxn=max(u.step,maxn);
  25. 25 vis[u.step]++;
  26. 26 }
  27. 27 for(int i=0;i<p[u.data].size();i++){
  28. 28 Q.push(NODE(p[u.data][i],u.step+1));
  29. 29 }
  30. 30 }
  31. 31 }
  32. 32 int main()
  33. 33 {
  34. 34 ios::sync_with_stdio(false);
  35. 35 cin>>n>>m;
  36. 36 for(int i=0;i<m;i++){
  37. 37 cin>>node>>k;
  38. 38 int t;
  39. 39 for(int j=0;j<k;j++){
  40. 40 cin>>t;
  41. 41 p[node].push_back(t);
  42. 42 }
  43. 43 }
  44. 44 bfs(1,1);
  45. 45 cout<<vis[1];
  46. 46 for(int i=2;i<=maxn;i++){
  47. 47 cout<<" "<<vis[i];
  48. 48 }
  49. 49 cout<<endl;
  50. 50 return 0;
  51. 51 }

 

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号