pat 1004

1004.c

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    struct node *child;
    struct node *brother;
} node_t;

void count_leaf(node_t *node, int *counts, int height, int *depth)
{
    *depth = height;

    while (node) {
        if (node->child) {
            count_leaf(node->child, counts, height+1, depth);
        } else {
            counts[height]++;
        }
        node = node->brother;
    }
}

node_t nodes[110];
int counts[110];

int main()
{
    int N, M;
    int i, j;
    scanf("%d %d", &N, &M);

    for (i = 0; i < M; i++) {
        int p_id = 0;
        int c_id = 0;
        int c_num = 0;

        scanf("%d %d", &p_id, &c_num);

        scanf("%d", &c_id);
        nodes[p_id].child = &nodes[c_id];
        node_t *p = &nodes[c_id];
        for (j = 1; j < c_num; j++) {
            scanf("%d", &c_id);
            p->brother = &nodes[c_id];
            p = p->brother;
        }
        p->brother = NULL;
    }

    int depth = 0;
    count_leaf(&nodes[1], counts, 0, &depth);

    for (i = 0; i < depth; i++) {
        printf("%d ", counts[i]);
    }

    printf("%d", counts[depth]);

    return 0;
}