PAT A1094 The Largest Generation (25分)

PAT A1094 The Largest Generation (25分)
PAT A1094 The Largest Generation (25分)

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
const int N = 110;
struct node{
    int deep;
    vector<int> child;
}Node[N];//1..N-1
int n,m;
int maxdeep = 0;
vector<int>generation;
void layerOrder(int root){
    queue<int> q;
    q.push(root);
    Node[root].deep = 1;
    generation.push_back(1);
    while(q.empty()==false){
        int front = q.front();
        q.pop();
        int tempdeep = Node[front].deep;
        for(int i = 0;i<Node[front].child.size();i++){
            int childid = Node[front].child[i];
            Node[childid].deep = tempdeep+1;
            if(generation.size()<=tempdeep){//0->1 1->2
                generation.push_back(1);
                
            }else{
                generation[tempdeep] += 1;
            }
            q.push(childid);
        }
    }
    return;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=m;i++){//m lines
        int id,childnum,childid;
        scanf("%d",&id);
        scanf("%d",&childnum);
        for(int j = 0;j<childnum;j++){
            scanf("%d",&childid);
            Node[id].child.push_back(childid);
        }
    }
    layerOrder(1);
    int max = 0;
    int layer = 0;
    for(int i = 0;i<generation.size();i++){
        if(generation[i]>max){
            max = generation[i];
            layer = i+1;
        }
    }
    printf("%d %d",max,layer);
    return 0;
}
上一篇:.Net Core中GC调优


下一篇:理解 python GC