PAT 1004 Counting Leaves_1004 counting leaves 节点3-CSDN博客

本文链接：https://blog.csdn.net/cham_3/article/details/9715199

本文介绍了一道PAT竞赛题目的解题思路与实现方法，重点在于使用广度优先搜索和邻接表来解决族谱中同一辈无子节点的计数问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

最近刚开始做PAT的练习题,太久没敲题目,手和脑袋都生锈了.

本题的题意就是要我们在family tree族谱上找出同一辈(与根节点距离相等的节点)没有child的节点个数.

博主在做这道题时用的是广搜+连接表;

主要注意的地方在于:

输入的节点编号不一定是连续的;
父节点的编号不一定小于子节点的编号;

参考代码如下,大牛勿喷:

#include<stdio.h>
int main()
{
	int n,m,l[110]={0},i,k,x,j,ls[110][110]={0},count=0,lk[110][110]={0};
	scanf("%d%d",&n,&m);
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&k,&x);
			for(j=1;j<=x;j++)
				scanf("%d",&ls[k][j]);
			ls[k][0]=x;
		}
        l[1]=0;	
		for(i=1;i<100;i++)
		{
			for(j=1;j<=ls[i][0];j++)
				l[ls[i][j]]=l[i]+1;
		} //广搜来标记各个节点离根节点距离
      	for(i=1;i<100;i++)
      	{
      		k=lk[l[i]][0]+1;
      	    if(l[i]==0)
                continue;
      	    lk[l[i]][k]=i;
      	    lk[l[i]][0]++;
      	}    //用lk记录到根节点距离相等的节点
      	if(ls[1][0]==0)
      	printf("1");
      	else
      	printf("0");
      	for(i=1;i<100;i++)
      	{
      	    if(lk[i][0]==0)
      	    break;
      	    count=0;
      	    for(j=1;j<=lk[i][0];j++)
      	    {
      	        if(ls[lk[i][j]][0]==0)
      	        count++;
      	    }    
      	    printf(" %d",count);
      	}    //统计距离根节点i的叶节点个数并输出
		putchar(10);
	return 0;
}