计蒜客家谱（dfs求直系后代数）
这一天蒜头君拿到了自己家的家谱，蒜头君便想知道，在自己家的家谱中，每位祖先有多少直系后代（直系后代包括他的孩子和他孩子的直系后代）。但是家族历史源远流长，家谱实在太庞大了，自己一个人完全数不过来。热心的你便自告奋勇帮蒜头君写一个程序，来统计每位祖先有多少直系后代。
输入格式
输入的第一行有一个整数 n(1≤n≤100000)，表示家谱中的总人数。
接下来读入 n−1 行，每行有两个整数 x(1≤x≤n), y(1≤y≤n)，表示 x 是 y 的父母。
输出格式
输出 n 行，每行有一个整数，表示第 i 个人有多少个直系后代。
样例输入
4
1 2
1 3
2 4
样例输出
3
1
0
0
#include <iostream> #include <vector> using namespace std; vector<int> a[100005]; //建立100005个动态数组 bool b[100005]; //标记，用来寻找辈分最大的人 int n; int ans[100005]; int dfs(int x){ int res=0; //直系后代的人数 for(int i=0;i<a[x].size();i++){ res+=dfs(a[x][i]); } //遍历自己第一代的儿女，继续调用该函数 ans[x]=res; //人数保存 return res+1; //每遇到一个加一 } int main(){ int x,y,root; cin>>n; for(int i=0;i<n-1;i++){ cin>>x>>y; a[x].push_back(y); //将x的第一代后辈插入一个动态数组中 b[y]=1; //标记，证明y不是父节点 } for(int i=0;i<n-1;i++){ if(!b[i]){ root=i; //寻找父节点的下标 } } dfs(root); //dfs一下 for(int i=1;i<=n;i++){ cout<<ans[i]<<endl; //打印每个人的直系后代 } return 0; }
