【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");
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/99004796