子树的节点个数

有一个棵树，树上有 n 个结点。结点的编号分别为 1…n，其中 1 是树的根结点。现在希望你帮忙计算每个结点作为根结点的子树分别有多少结点。

输入格式
第一行输入一个数字 n，代表树上结点的个数。（2≤n≤1000）接下来的 n−1 行，每行俩个数字 a，b，代表结点 a 到结点 b 有一条边。

输出格式
按编号顺序输出每个结点作为根结点的子树，分别有多少结点，中间用空格分开。

样例输入
5
1 4
1 3
3 2
3 5
样例输出
5 1 3 1 1

#include<bits/stdc++.h>

using namespace std;
vector<int> tree[1001];

int dfs(int x) {
    if (tree[x].empty())
        return 0;
    else {
        int count0 = tree[x].size();
        for (int i = 0; i < tree[x].size(); i++) {
            count0 += dfs(tree[x][i]);
        }
        return count0;
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
    }
    for (int i = 1; i <= n; i++) {
        if (tree[i].empty())
            cout << '1';
        else
            cout << dfs(i) + 1;
        if (i < n)
            cout << ' ';
    }
    return 0;
}

最后

以上就是活泼小土豆为你收集整理的子树的节点个数的全部内容，希望文章能够帮你解决子树的节点个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。