PAT甲级1004

#include <iostream> #include <queue> using namespace std; int tree[100][100]={0}; int layer,level[100]={0}; int noChild[100]={0}; void BFS(int root){ queue<int> Q; Q.push(root); int lastNode=root,newLastNode; layer=1; while(!Q.empty()){ int t=Q.front(); Q.pop(); int k=0; if(tree[t][k]!=0){ while(tree[t][k]!=0){ Q.push(tree[t][k]); k++; } newLastNode=tree[t][k-1]; }else{ noChild[layer]++; } if(t==lastNode){ lastNode=newLastNode; layer++; } } } int main(int argc, char** argv) { int N,M,father,numberChild,child; cin>>N>>M; for(int i=0;i<M;i++){ cin>>father>>numberChild; for(int j=0;j<numberChild;j++){ cin>>child; tree[father][j]=child; } } BFS(1); for(int i=1;i<layer;i++){ if(i==1){ cout<<noChild[i]; }else{ cout<<" "<<noChild[i]; } } return 0; }