PAT 1004
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
Input
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 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.
Output
For each test case, you are supposed to count those family members who have no childfor 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
2 1
01 1 02Sample Output
0 1
一、深度优先 #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
map<int,vector<int> >childs;
int record[101]={0};
//DSF（id,level）表示以结点id为根节点，统计第level层的叶子节点数量
void DFS(int id,int level){
if(childs[id].empty()){
record[level]++;
return;
}
vector<int>::iterator ite = childs[id].begin();
while(ite!=childs[id].end()){
DFS(*ite,level+1);
++ite;
}
}
int main(){
int n,m,id,k,childId,i,leaveCnt,cnt;
scanf("%d %d",&n,&m);
leaveCnt = n-m;//叶子节点数:总节点减去非叶子节点
while(m--){
scanf("%d %d",&id,&k);
while(k--){
scanf("%d",&childId);
childs[id].push_back(childId);
}
}
DFS(1,0);
printf("%d",record[0]); //第一层有几个叶子节点
cnt = record[0];//叶子节点计数
for(i=1;cnt<leaveCnt;i++){
printf(" %d",record[i]); //第i层有多少个叶子节点
cnt += record[i];
}
printf("\n");
return 0;
} 二、广度优先
#include <iostream>
#include <map>
#include <queue>
using namespace std;
int N,M,lvnull[100]={0};
map<int,vector<int> > imap;
queue<int> level,ids;//level:对应id的深度，ids:记录节点id
int main()
{
int i,j,id,k,tmp;
cin>>N>>M;
for(i=0;i!=M;++i){
cin>>id>>k;
for(j=1;j<=k;++j){
cin>>tmp;
imap[id].push_back(tmp);
}
}
int depth = 0;
ids.push(1);//根结点入队
level.push(0);//0层入队
while(!ids.empty()){//节点空
int id = ids.front();
int lvl = level.front();
ids.pop(); //节点队列：出队
level.pop();//层队列：出队
if(lvl>depth) //记录深度
depth = lvl;
if(imap[id].empty())
lvnull[lvl]++;//第lvl层的叶子节点+1
for(i=0;i!=imap[id].size();++i){//遍历节点id的孩子
ids.push(imap[id][i]);//节点id的孩子i入队
level.push(lvl+1);//id有多少个孩子，lvl+1入队几次
}
}
for(i=0;i!=depth+1;++i){
cout<<lvnull[i];
if(i != depth)
cout<<" ";
}
return 0;
}