首页 > > 程序设计 > C/C++ >

1004 Counting Leaves （30 分）（树的遍历）

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

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

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 }