The Largest Generation (25)

#include <iostream>
#include <vector>
using namespace std;
const int maxn=110;
int n,m,father,childnum,child;
int levelnum[maxn]={0},maxlevel=1,maxnum=0;   //设置一个某层结点个数数组，结点个数最多的层次及该层层号
vector<int> Node[maxn];                       //树，每个Node[]里面存储子结点编号
void DFS(int now,int level){                  //DFS遍历树（传入结点号与层号）
    levelnum[level]++;
    if(levelnum[level]>maxnum){               //更新结点最多的层号及结点个数
        maxnum=levelnum[level];
        maxlevel=level;
    }
    for(int i=0;i<Node[now].size();i++)       //遍历当前结点的子树
        DFS(Node[now][i],level+1);
}
int main(){  cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>father>>childnum;
        for(int j=0;j<childnum;j++){
            cin>>child;
            Node[father].push_back(child);
        }
    }
    DFS(1,1);
    cout<<maxnum<<" "<<maxlevel;
    return 0;
} 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		Queue<Integer> q = new LinkedList<Integer>();
		int n = in.nextInt();
		int m = in.nextInt();
		int[] num = new int[n+1];
		int[][] ar = new int[n+1][100];
		
		for (int i = 0; i < m; i++) {
			int k = in.nextInt();
			num[k] = in.nextInt();
			for (int j = 0; j < num[k]; j++) {
				ar[k][j] = in.nextInt();
			}
		}
		int max = 1;
		int count = 1;
		int h = 0;
		int maxh = 1;
		q.add(1);
		while (!q.isEmpty()) {
			h++;
			if (count > max) {
				max = count;
				maxh = h;
			}
			
			int t = 0;
			for (int i = 0; i < count; i++) {
				int v = q.remove();
				for (int j = 0; j < num[v]; j++) {
					q.add(ar[v][j]);
				}
				t += num[v];
			}
			count = t;
		}
		in.close();	
		
		System.out.println(max + " " + maxh);
	}
	
}

#include<bits/stdc++.h>

using namespace std;


int main()
{
    vector<int> son[105];
    int N,M;
    cin>>N>>M;
    while(M--)
    {
        int i, k, t;
        cin>>i>>k;
        while(k--)
        {
            cin>>t;
            son[i].push_back(t);
        }
    }
    {
        int cnt=0, cnt_pre, cnt_now, level(1),r_l;
        queue<int> Q;
        Q.push(1);
        cnt_pre = 1;
        while(!Q.empty())
        {
            cnt_now = 0;
            ++level;
            while(cnt_pre--)
            {
                int now = Q.front();
                Q.pop();
                for(int i=0; i<son[now].size(); ++i,++cnt_now)
                    Q.push(son[now][i]);
            }
            cnt_pre = cnt_now;
            if(cnt_now > cnt)
            {
                cnt = cnt_now;
                r_l = level;
            }
        }
        cout<<r_l<<" "<<cnt<<endl;
    }
    return 0;
}

#include <stdio.h>
#include <malloc.h>

int get_gen(int *family, int child) {
	int gen = 1;
	while (family[child] != child) {
		gen++;
		child = family[child];
	}
	return gen;
}
int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	int *family = (int *) malloc((N + 1) * sizeof(int));
	for (int i = 0; i <= N; ++i) {
		family[i] = i;
	}
	for (int i = 0; i < M; ++i) {
		int parent;
		int child_num;
		scanf("%d %d", &parent, &child_num);
		for (int j = 0; j < child_num; ++j) {
			int child;
			scanf("%d", &child);
			family[child] = parent;
		}
	}

	int *gen = (int *) malloc((N + 1) * sizeof(int));
	for (int i = 0; i <= N; ++i) {
		gen[i] = 0;
	}
	for (int i = 1; i <= N; ++i) {
		gen[get_gen(family, i)]++;
	}
	int max_gen = 0, max_member = 0;
	for (int i = 1; i <= N; ++i) {
		if (gen[i] > max_member) {
			max_member = gen[i];
			max_gen = i;
		}
	}
	printf("%d %d", max_member, max_gen);
	free(family);
	free(gen);
	return 0;
}

//使用map存储数据，BFS+队列处理数据，优先队列存储结果
#include <bits/stdc++.h>

using namespace std;

//问题表示
int N, M;
map<string, vector<string>> node;			//{01:{03, 02, 04, 05}} 

//问题求解
queue<string> qu;

struct Cmp
{
	bool operator()(pair<int, int> p1, pair<int, int> p2)
	{
		return p1.second < p2.second;
	}
};

priority_queue<pair<int, int>, vector<pair<int, int>>, Cmp> res;			//res:{{代， 总个数},...}

void create_instance()
{
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		string father_code;
		int son_num;
		cin >> father_code >> son_num;
		for (int i = 0; i < son_num; i++)
		{
			string son_code;
			cin >> son_code;
			node[father_code].push_back(son_code);
		}
	}
}

void bfs()
{
	for (auto code : node["01"])
		qu.push(code);
	int cnt = 2;
	res.push({ 1, 1 });
	res.push({ cnt, qu.size() });
	while (!qu.empty())
	{
		int qu_num = qu.size();
		for (int i = 0; i < qu_num; i++)
		{
			string son = qu.front();
			qu.pop();
			if (node.find(son) != node.end())
			{
				for (auto code : node[son])
					qu.push(code);
			}
		}
		res.push({ ++cnt, qu.size() });
	}
}

int main()
{
	create_instance();
	bfs();
	cout << res.top().second << " " << res.top().first << endl;
}

#include<iostream>
using namespace std;
int n,m;
int f[100]={0},g[100]={0};
int getg(int x)
{
    if(g[x]==-1) return g[x]=getg(f[x])+1;
    return g[x];
}
int main()
{
    fill(g,g+100,-1);g[1]=1;
    int i,j,x,num,son;
    cin>>n>>m;
    for(i=0;i<m;i++)
    {
        cin>>x>>num;
        for(j=0;j<num;j++)
        {
            cin>>son;
            f[son]=x;
        }
    }
    int a[n]={0};
    for(i=1;i<=n;i++)
        a[getg(i)]++;
    int max=1,id=1;
    for(i=1;i<n;i++)
    {
        if(a[i]>max)
        {
            max=a[i];
            id=i;
        }
    }
    cout<<max<<' '<<id;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

int getGenerate(int *family, int child)
{     int gen = 1;     while(family[child] != child)     {         gen++;         child = family[child];     }     return gen;
}

int main()
{     int N,M;     cin>>N>>M;     int *family = (int *)malloc((N+1)*sizeof(int));     for(int i=0;i<=N;i++)         family[i] = i;     for(int i=0;i<M;i++)     {         int parent;         int child_num;         cin>>parent>>child_num;         for(int j=0;j<child_num;j++)         {             int child;             cin>>child;             family[child] = parent;         }     }     int *gen = (int *)malloc((N+1)*sizeof(int));     for(int i=0;i<=N;i++)         gen[i] = 0;     for(int i=1;i<=N;i++)         gen[getGenerate(family, i)]++;     int maxGen = 0, maxMember = 0;     for(int i=1;i<=N;i++)         if(gen[i] > maxMember)         {             maxMember = gen[i];             maxGen = i;         }     cout<<maxMember<<" "<<maxGen<<endl;     free(family);     free(gen);     return 0;
}

#include<bits/stdc++.h>
using namespace std;

int N, M;

struct Person{
	string ID;
	vector<string> child;
};
vector<Person> persons;//所有人


set<string> isChild;//是某个人的孩子,存这,用来找第一代


vector<string> getChild(string ID){//根据ID来获取此人的孩子
	vector<string> res;
	for (int i = 0; i < M; i++){
		if (persons[i].ID == ID)return persons[i].child;
	}
	return res;
}

int main(){
	ios::sync_with_stdio(false);
	cin >> N >> M;

	persons.resize(M);

	int k;
	for (int i = 0; i < M; i++){
		
		cin >> persons[i].ID;
		cin >> k;
		persons[i].child.resize(k);
		for (int j = 0; j < k; j++){
			cin >> persons[i].child[j];
			isChild.insert(persons[i].child[j]);
		}

	}

	//bfs,初始化,第一代人先入队列1
	vector<string> rootGen;
	for (int i = 0; i < M; i++){
		if (find(isChild.begin(), isChild.end(), persons[i].ID) == isChild.end()){//初代都不在isChild集合里
			rootGen.push_back(persons[i].ID);
		}
	}
	int MaxPop = rootGen.size();
	int MaxLevel = 1;
	int level = 1;

	//循环队列,一队列一代人,前一代人从某个队列出完,后一代人正好全部进入另一个队列

	queue<string> myQue1;
	queue<string> myQue2;
	int PushSize = 0;
	for (int i = 0; i < rootGen.size(); i++){
		myQue1.push(rootGen[i]);
		PushSize++;
	}

	set<string> Gen;//可能会重复所以用set保存,最后计数
	while (!myQue1.empty() || !myQue2.empty()){
		if (!myQue1.empty()){
			Gen.clear();
			while (!myQue1.empty()){
				string front = myQue1.front();
				Gen.insert(front);
				myQue1.pop();
				vector<string> child = getChild(front);
				for (int i = 0; i < child.size(); i++){
					myQue2.push(child[i]);
				}
			}
			int pop = Gen.size();
			if (pop>MaxPop){
				MaxPop = pop;
				MaxLevel = level;
			}
			level++;
		}
		else if (!myQue2.empty()){
			Gen.clear();
			while (!myQue2.empty()){
				string front = myQue2.front();
				Gen.insert(front);
				myQue2.pop();
				vector<string> child = getChild(front);
				for (int i = 0; i < child.size(); i++){
					myQue1.push(child[i]);
				}
			}
			int pop = Gen.size();
			if (pop>MaxPop){
				MaxPop = pop;
				MaxLevel = level;
			}
			level++;

		}
	}

	cout << MaxPop << " " << MaxLevel << endl;



	return 0;
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		Node[] nodes = new Node[n+1];
		for(int i = 0;i<m;i++){
			int id = in.nextInt();
			int k = in.nextInt();
			Node node = new Node(id,k);
			for(int j = 0;j<k;j++)
				node.addChild(in.nextInt());
			nodes[id] = node;
		}
		int generation = 0;
		int size = 0;
		int maxs = -1;
		int maxg = -1;
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(nodes[1]);
		while(!queue.isEmpty()){
			generation++;
			size = queue.size();
			if(size>maxs){
				maxs = size;
				maxg = generation;
			}
			if(maxs>n/2)
				break;
			while(size-- != 0){
				Node top  = queue.poll();
				while(top!=null&&!top.isEmpty()){
					queue.add(nodes[top.getChild()]);
				}
			}
			
		}
		System.out.println(maxs+" "+maxg);
	}
	
	private static class Node{
		int id;
		int[] children;
		int pos = 0;
		public Node(int id, int k) {
			this.id = id;
			this.children = new int[k];
		}
		public void addChild(int id){
			children[pos++]=id;
		}
		public int getChild(){
			return children[--pos];
		}
		public boolean isEmpty(){
			return pos==0;
		}
		
	}
}

#include<bits/stdc++.h>
using namespace std;

const int Max=110;
vector<int> child[Max];
int Hashtable[Max]= {0};

void DFS(int index,int level) {
	Hashtable[level]++;
	for(int i=0; i<child[index].size(); i++) {
		DFS(child[index][i],level+1);
	}
}

int main() {
	int n,m,father,k,ch;
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++) {
		scanf("%d %d",&father,&k);
		for(int j=0; j<k; j++) {
			scanf(" %d",&ch);
			child[father].emplace_back(ch);
		}
	}
	DFS(1,1);
	int MaxV=0,ans;
	for(int i=1; i<Max; i++) {
		if(Hashtable[i]>MaxV) {
			MaxV=Hashtable[i];
			ans=i;
		}
	}
	printf("%d %d\n",MaxV,ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m,p,k,c;
int f_num,f_l;
vector<int> childs[100];
queue<int> q;
int main(){
    cin>>n>>m;
    while(m--){
        cin>>p>>k;
        while(k--){
            cin>>c;
            childs[p].push_back(c);
        }
    }
    q.push(1);int l=1;int p_num=1;
    //BFS
    while(!q.empty()){
        l++;int n_num=0; 
        for(int i=0;i<p_num;i++){
            int tp=q.front();q.pop();
            for(int j=0;j<childs[tp].size();j++){
                q.push(childs[tp][j]);
            }
            n_num+=childs[tp].size();
        }
        if(n_num>f_num){
            f_num=n_num;f_l=l;
        }
        p_num=n_num;
    }
    cout<<f_num<<" "<<f_l;
}

#include <iostream>
(720)#include <stdio.h>
#include <string>
(765)#include <string.h>
#include <queue>
(789)#include <algorithm>
#include <math.h>
(865)#include <map>
#include <stack>
(850)#include <set>
#include <vector>
(721)#include <cctype>
#define INF 1e9
using namespace std;
string Int2Str[10]={"0","1","2","3","4","5","6","7","8","9"};

int main(){
    int total, n;
    while(cin>>total>>n){
        vector<int> family[total+1];
        int root=1;
        for(int i=0; i<n; i++){
            int id, k;
            cin>>id>>k;
            while(k--){
                int x;
                cin>>x;
                family[id].push_back(x);
            }
        }
        queue<int> Q;
        Q.push(root);
        int generation=0, population=0;
        int buf[110], level=1;
        memset(buf, 0, sizeof(buf));
        while(total){
            int len=Q.size();
            for(int i=0; i<len; i++){
                int x=Q.front();
                Q.pop();
                buf[level]++;
                for(int j=0; j<family[x].size(); j++)
                    Q.push(family[x][j]);
            }
            total-=len;
            level++;
        }
        for(int i=1; i<level; i++){
            if(buf[i]>population){
                population=buf[i];
                generation=i;
            }
        }
        cout<<population<<" "<<generation<<endl;
    }
}

a = list(map(int,input().split()))
d,m,p,q,r = {},['01'],1,1,1
for i in range(a[1]):
    b = input().split()
    d[b[0]] = b[2:]
while m:
    n = []
    for i in m:
        if i in d:
            n.extend(d[i])
    m,q = n,q + 1
    if len(m) > p:
        p,r = len(m),q

print(p,r)

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
public class A1005
{
    private static int M, N;
    private static int[][] familyTree;// 看成有向图 用邻接矩阵存储
    private static Queue<Integer> childQueue;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        familyTree = new int[N + 1][N + 1];// 从01开始，所以大小为N+1，弃去一行一列
        childQueue = new LinkedList<>();
        for (int i = 0; i < M; i++)
        {
            int v = sc.nextInt();
            int numOfChild = sc.nextInt();
            for (int j = 0; j < numOfChild; j++)
            {
                int child = sc.nextInt();
                familyTree[v][child] = 1;
            }
        }
        sc.close();
        int result = 1;
        int resLevel = 1;
        childQueue.add(1);
        int numOfChild = 1;
        for (int level = 1; !childQueue.isEmpty(); level++)
        {
            int index = numOfChild;
            numOfChild = 0;
            for (int i = 0; i < index; i++)
            {
                int child = childQueue.poll();
                for (int j = 1; j < N + 1; j++)
                {
                    if (familyTree[child][j] == 1)
                    {
                        childQueue.add(j);
                        numOfChild++;
                    }
                }
            }
            if(numOfChild>result)
            {
                result = numOfChild;
                resLevel = level+1;
            }
        }
        System.out.print(result+" "+resLevel);
    }
}

就是一个BFS遍历树，这里要注意的是需要特判节点最多的是不是最后一层，如果不特判的话在牛客可以过但是在PAT官网上是过不去的，希望能帮到牛客过了但是PAT WA还没找到问题的人

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m,ans_num=1,ans_gen=1,prev_gen=1,prev_num=1;
vector<int> v[105];
struct node
{
    int gen,id;
    node(int gen=1,int id=1)
    {
        this->gen=gen;
        this->id=id;
    }
};
queue<node> q;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int id,k;
        scanf("%d %d",&id,&k);
        for(int j=0;j<k;j++)
        {
            int idk;
            scanf("%d",&idk); 
            v[id].push_back(idk);//记录每个点的子节点 
        }
    }
    for(int i=0;i<v[1].size();i++)
        q.push(node(2,v[1][i]));//第一层先压队列 

    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(now.gen!=prev_gen)//每次到了全新一层就判断是否更新答案与更新层数 
        {
            if(prev_num>ans_num)
            {
                ans_num=prev_num;
                ans_gen=prev_gen;
            }
            prev_gen=now.gen;
            prev_num=0;
        }
        prev_num++;
        for(int i=0;i<v[now.id].size();i++)
            q.push(node(prev_gen+1,v[now.id][i]));
    }
    if(prev_num>ans_num)//这里注意判断一下，因为可能节点最多的在最后一层 
    {
        ans_num=prev_num;
        ans_gen=prev_gen;
    }
    printf("%d %d",ans_num,ans_gen);
    return 0;
}

	def loopone(lstin):
    global con
    tem = []
    for i in range(0,len(lstin)):
        for j in range(2,len(lstin[i])):
            for k in lst:
                if k[0] == lstin[i][j]:
                    con = con+k[1]
                    tem.append(k)
                    lst.remove(k)
    return tem



	def loop(lstin):
    global con
    tem = []
    for j in range(2,len(lstin)):
        for k in lst:
            if k[0] == lstin[j]:
                con = con+k[1]
                tem.append(k)
                lst.remove(k)
    return tem



	n,m = map(int,input().split())
temlst,conlst,lst,sublst,gencon = [],[],[],[],[1]
con = 0
for i in range(0,m):
    lst.append(list(map(int,input().strip().split())))
for i in range(0,len(lst)):
    if lst[i][0]==1:
        temlst = list(lst[i])
        con = con + lst[i][1] 
        del lst[i]
        break
gencon.append(con)
con = 0
index = 0
temlst = loop(temlst)
gencon.append(con)
con = 0
conlst = list(temlst)
while len(lst)>0:
    if isinstance(conlst[0], list) and len(conlst)>0:
        conlst = loopone(conlst)
        gencon.append(con)
        con = 0
    elif isinstance(conlst[0], int) and len(conlst)>0:
        conlst = loop(conlst)
        gencon.append(con)
        con = 0
    elif len(conlst)==0:
        break
ma = max(gencon)
mindex = 0
for i in range(0,len(gencon)):
    if gencon[i]==ma:
        mindex = i+1
print(str(ma)+" "+str(mindex))