还是代码写的少,有点手生,写了好久。。。。
题目很明了,求一个家族树上每一代人有多少没有孩子的,就是求树的每一层上有多少没有子结点的,层次遍历计数就好了。
//1004
//数组a用来存数据,第一个维度指结点编号,第二个维度中a[i][0]表示结点i是否有孩子
//a[i][1]为k,a[i][2]以及以后表示i结点的所有孩子编号
int a[100][205];
int main(){
int n,m,nod,k;
while(scanf("%d%d",&n,&m)!=EOF&&n){
for(int p=0;p<m;p++){
scanf("%d %d",&nod,&k);
a[nod][0] = 1;
a[nod][1] = k;
for(int i=2;i<=a[nod][1]+1;i++) scanf("%d",&a[nod][i]);
}
queue<int> q;
vector<int> ans;
bool onlyroot = false;
int cnt = 0 ,all = 0;
q.push(1);
if(!a[1][0]) {onlyroot = true;ans.push_back(1);}//如果只有一个根节点
while(1){
if(onlyroot) break; //如果只有一个根节点
if(all>=n) break;//所有点都算过了
//所有这一层出队,下一层入队
int len = q.size();
all+=len;
while(len--)
{
int t = q.front();q.pop();
if(!a[t][0]) cnt++;
for(int i=0;i<a[t][1];i++)
{
q.push(a[t][i+2]);
}
}
ans.push_back(cnt);
cnt = 0;
}
for(int i=0;i<ans.size();i++)
{
printf("%d",ans[i]);
if(i<ans.size()-1) printf(" ");
}
printf("\n");
}
return 0;
}