题目

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.

Input Specification:

Each input file contains one test case. Each case starts with a line containing $0<N<100$ , the number of nodes in a tree, and $M$ ( $<N$ ), the number of non-leaf nodes. Then $M$ lines follow, each in the format:

1

ID K ID[1] ID[2] ... ID[K]

where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.

The input ends with $N$ being 0. That case must NOT be processed.

Output Specification:

For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.

The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output 0 1 in a line.

Sample Input:

1
2

2 1
01 1 02

Sample Output:

1

0 1

思路

虽然是30分的题，但是好像比1003还简单。

同样使用了邻接链表（adjacent list），数据结构如下：

  • Member（Vertex）：表示一个家庭成员，我使用了两个结构成员：
  • level，表示这个人在家谱中的辈分，最高的辈分是0，辈分越低，level越大
  • child，指向Child结构变量，即链表的第一个节点
  • Child（Edge）：表示亲子关系，也使用了两个结构成员：
  • ID，表示这个孩子的ID
  • iter，指向相同父母的下一个孩子Child变量

读取数据，建立邻接链表。初始化01节点的level为0，其他level为INF。

然后按level从0开始，依次遍历所有Member，找出相应辈分的家庭成员。这时分两种情况：这个成员没有孩子，那么需要进行计数；这个成员有孩子，那么需要更新他们的level值为这个成员的level+1，以便下一次遍历时找到他们。

使用一个标记表明何时不需再遍历，我用的是记录人数，当之前所有level的人数已经是总人数，那么说明已全部遍历，此时退出循环。

代码

Github最新代码，欢迎交流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <stdio.h>

#define MAX 999

typedef struct Member *Member;
typedef struct Child *Child;

struct Member{
	int level;
	Child child;
};

struct Child{
	int ID;
	Child iter;
};

int main()
{
	int N, M, ID, cID, K;
	struct Member nodes[100];
	struct Child children[100];

	/* Read data and initiate a adjacent list */
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		nodes[i].level = MAX;
		nodes[i].child = NULL;
	}
	nodes[1].level = 0;         /* root node at level 0 */
	for (int i = 0, k = 0; i < M; i++) {
		scanf("%d %d", &ID, &K);
		for (; K--; k++) {
			scanf("%d", &cID);
			children[k].ID = cID;
			children[k].iter = nodes[ID].child;
			nodes[ID].child = &children[k];
		}
	}

	/* For every level, find leaf nodes */
	int n = N, count;
	for (int level = 0; n; level++) {
		count = 0;
		for (int i = 1; i <= N; i++)
			if (nodes[i].level == level) {
				n--;
				if (nodes[i].child == NULL)
					count++;
				/* set the children to next level */
				for (Child c = nodes[i].child; c; c = c->iter)
					nodes[c->ID].level = level + 1;
			}

		printf("%d%c", count, n ? ' ' : '\0');
	}

	return 0;
}