# PAT Advanced 1004. Counting Leaves()-其他

## PAT Advanced 1004. Counting Leaves()

### 1. Problem Description:

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

### 2. 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:

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

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

``ID``
``K``
``ID``
``01``

The input ends with \(N\) being 0. That case must NOT be processed.

### 3. 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 is the root and is its only child. Hence on the root level, there is leaf node; and on the next level, there is leaf node. Then we should output in a line.

``01``
``02``
``01``
``0``
``1``
``0 1``

### 4. Sample Input:

``````2 1
01 1 02
``````

### 5. Sample Output:

``````0 1
``````

### 6. Performance Limit:

``````Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB
``````

### 思路：

``tree[MAX_SIZE][MAX_SIZE]``
``traverseTree()``
``levelNow``
``res``
``res``
``map<int, int>``
``maxLevel``
``visitFlag``

### My Code & Result:

``````#include <iostream>
//#include <map>
#define MAX_SIZE 100

using namespace std;

void traverseTree(int tree[MAX_SIZE][MAX_SIZE], int idNow, int levelNow, int *maxLevel, int res[MAX_SIZE], int visitFlag[MAX_SIZE]);

int main(void)
{
int tree[MAX_SIZE][MAX_SIZE] = {0};
int n=0, m=0;
int tempId=0, tempCount=0, tempChild=0;
int i=0, j=0; // iterator
// map<int, int> res; // count every level's leaf node
int maxLevel=0, res[MAX_SIZE+1] = {0}; // use array to count, for map can't count zero
int visitFlag[MAX_SIZE] = {0}; // make sure all node count once

cin >> n >> m;

if(!n) return 0; // n==0, return directly

for(i=0; i<m; ++i)
{
cin >> tempId >> tempCount;
for(j=0; j<tempCount; ++j)
{
cin >> tempChild;
tree[tempId][tempChild] = 1;
}
}

traverseTree(tree, 1, 1, &maxLevel, res, visitFlag);

for(i=1; i<=maxLevel; ++i)
{
if(i==1) cout << res[i];
else cout << " " << res[i];
}
cout << endl;

// for(const auto &w: res)
// {
//     cout << w.first << ": " << w.second << endl;
// }

return 0;
}

void traverseTree(int tree[MAX_SIZE][MAX_SIZE], int idNow, int levelNow, int *maxLevel, int res[MAX_SIZE], int visitFlag[MAX_SIZE])
{
int i=0; // iterator
int flag=0; // have child flag

if(levelNow > *maxLevel) *maxLevel = levelNow;

for(i=0; i<MAX_SIZE; ++i)
{
if(tree[idNow][i])
{
flag = 1;
traverseTree(tree, i, levelNow+1, maxLevel, res, visitFlag);
}
}

if(!flag && !visitFlag[idNow]) // have no child && visit first time
{
visitFlag[idNow] = 1;
++res[levelNow];
}

// if(!flag) ++res[levelNow]; // have no child

return;
}
``````
``````Compiler
C++ (g++)
Memory
456 / 65536 KB
Time
4 / 400 ms
``````
————————

### 1. Problem Description:

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

### 2. 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:

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

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

``ID``
``K``
``ID``
``01``

The input ends with \(N\) being 0. That case must NOT be processed.

### 3. 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 is the root and is its only child. Hence on the root level, there is leaf node; and on the next level, there is leaf node. Then we should output in a line.

``01``
``02``
``01``
``0``
``1``
``0 1``

### 4. Sample Input:

``````2 1
01 1 02
``````

### 5. Sample Output:

``````0 1
``````

### 6. Performance Limit:

``````Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB
``````

### 思路：

``tree[MAX_SIZE][MAX_SIZE]``
``traverseTree()``
``levelNow``
``res``
``res``
``map<int, int>``
``maxLevel``
``visitFlag``

### My Code & Result:

``````#include <iostream>
//#include <map>
#define MAX_SIZE 100

using namespace std;

void traverseTree(int tree[MAX_SIZE][MAX_SIZE], int idNow, int levelNow, int *maxLevel, int res[MAX_SIZE], int visitFlag[MAX_SIZE]);

int main(void)
{
int tree[MAX_SIZE][MAX_SIZE] = {0};
int n=0, m=0;
int tempId=0, tempCount=0, tempChild=0;
int i=0, j=0; // iterator
// map<int, int> res; // count every level's leaf node
int maxLevel=0, res[MAX_SIZE+1] = {0}; // use array to count, for map can't count zero
int visitFlag[MAX_SIZE] = {0}; // make sure all node count once

cin >> n >> m;

if(!n) return 0; // n==0, return directly

for(i=0; i<m; ++i)
{
cin >> tempId >> tempCount;
for(j=0; j<tempCount; ++j)
{
cin >> tempChild;
tree[tempId][tempChild] = 1;
}
}

traverseTree(tree, 1, 1, &maxLevel, res, visitFlag);

for(i=1; i<=maxLevel; ++i)
{
if(i==1) cout << res[i];
else cout << " " << res[i];
}
cout << endl;

// for(const auto &w: res)
// {
//     cout << w.first << ": " << w.second << endl;
// }

return 0;
}

void traverseTree(int tree[MAX_SIZE][MAX_SIZE], int idNow, int levelNow, int *maxLevel, int res[MAX_SIZE], int visitFlag[MAX_SIZE])
{
int i=0; // iterator
int flag=0; // have child flag

if(levelNow > *maxLevel) *maxLevel = levelNow;

for(i=0; i<MAX_SIZE; ++i)
{
if(tree[idNow][i])
{
flag = 1;
traverseTree(tree, i, levelNow+1, maxLevel, res, visitFlag);
}
}

if(!flag && !visitFlag[idNow]) // have no child && visit first time
{
visitFlag[idNow] = 1;
++res[levelNow];
}

// if(!flag) ++res[levelNow]; // have no child

return;
}
``````
``````Compiler
C++ (g++)
Memory
456 / 65536 KB
Time
4 / 400 ms
``````