深度优先搜索-族谱直系后代

题目描述：

sample input:
输入的第一行有一个整数n(1<=n<=100000),表示家谱的总人数，接下来读入n-1行，每行有一个整数，表示第i个人有多少个直系后代。

sample output:

输出n行，每行有一个整数，表示第i个人有多少个直系后代。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#include<utility>

#include<map>

using namespace std;

int n;

vector<int>v[100005];

bool f[100005];

int res[100005];

int dfs(int dx){

int re=0;

for(int i=0;i<v[dx].size();i++){

re+=dfs(v[dx][i]);

}

res[dx]=re;

return re+1;

}

int main(){

cin>>n;

int x,y;

for(int i=0;i<n-1;i++){

scanf("%d%d",&x,&y);

v[x].push_back(y);

f[y]=true;

}

int dx;

for(int i=1;i<=n;i++){

if(!f[i]){

dx=i;

break;

}

}

dfs(dx);

for(int i=1;i<=n;i++){

printf("%d\n",res[i]);

}

return 0;

}