【1094】The Largest Generation (25 分)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//key:用DFS递归遍历所有孩子结点，每次进入hashTable[level]加1
//另外key:Node[][]二维数组，Node[j]存放结点j的所有孩子结点编号
const int MAXN=110;//树的结点个数
vector<int> Node[MAXN];//树的静态写法，Node[i]存放结点i的孩子结点编号
int hashTable[MAXN]={0};  //记录每层的结点个数
void DFS(int index,int level){  //index为当前访问的结点编号
  hashTable[level]++; //第level层的结点个数加1
  for(int j=0;j<Node[index].size();j++){
    DFS(  Node[index][j] , level+1);  //遍历所有孩子结点，进行递归
  }
}
int main(){   
  int n,m,parent,k,child;
  scanf("%d%d",&n,&m);
  for(int i=0;i<m;i++){
    scanf("%d%d",&parent,&k); //父亲结点编号，孩子个数
    for(int j=0;j<k;j++){
      scanf("%d",&child);  //孩子结点编号,注意和for外面的scanf“隔开”
      Node[parent].push_back(child);  //建树
    }
  }
  DFS(1,1);  //根结点为1号结点，层号为1
  int maxLevel=-1,maxValue=0;
  for(int i=1;i<MAXN;i++){  //计算hashTable数组的最大值
    if(hashTable[i]>maxValue){
      maxValue=hashTable[i];
      maxLevel=i;
    }
  }
  printf("%d %d\n",maxValue,maxLevel);  //输出最大结点数与该层层号
  system("pause");
}