1004 Counting Leaves (30 分)(树的遍历)

2018-12-09 11:18:11来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

 

dfs遍历树

#include<bits/stdc++.h>

using namespace std;
vector<int>p[150];
int n,m;
int node ,k;
int vis[150];
int maxn=-1;
void dfs(int node,int step)
{
    if(p[node].empty()){
        vis[step]++;
        maxn=max(step,maxn);
    }
    else{
        for(int i=0;i<p[node].size();i++){
            dfs(p[node][i],step+1);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>node>>k;
        int t;
        for(int j=0;j<k;j++){
            cin>>t;
            p[node].push_back(t);
        }
    }
    dfs(1,1);
    cout<<vis[1];
    for(int i=2;i<=maxn;i++){
        cout<<" "<<vis[i];
    }
    cout<<endl;
    return 0;
}

 

bfs遍历求树

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

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:1001 A+B Format (20 分)

下一篇:1086 Tree Traversals Again (25 分)(二叉树的遍历)