欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-11-08 21:15:46
给出一棵树,问每一层各有多少叶子节点 dfs遍历树 bfs遍历求树 ......

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

 

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 }