1004 Counting Leaves （30 分）（樹的遍歷）

給出一棵樹，問每一層各有多少葉子節點

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 }