1694.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include<vector>
#include"stdlib.h"
using namespace std; 
int child[201],need[201];

int ch[201][200];

//int cmp(int i,int j)
int cmp(const void * i,const void * j)

{
	if(need[*((int *)i)]<need[*((int *)j)]) return 1;

	else if(need[*((int *)i)]>need[*((int *)j)]) return -1;

	return 0;
}

void doit(int a)
{
	int i,max;

	for(i=0;i<child[a];i++)
		if(need[ch[a][i]]==-1)doit(ch[a][i]);

	if(i==0){need[a]=1;return;}

	qsort(&ch[a][0],child[a],sizeof(int),cmp);

	max=0;
	for(i=0;i<child[a];i++)
		if(i+need[ch[a][i]]>max)max=i+need[ch[a][i]];

	need[a]=max;
}

int main()
{
	int i,j,n,t,a,node;

	cin>>t;

	while(t--)
	{
		cin>>node;
		for(i=0;i<node;i++)
		{
			cin>>a>>n;

			for(j=0;j<n;j++)
				cin>>ch[a][j];

			child[a]=j;
		}

		for(i=0;i<=node;i++)need[i]=-1;

		doit(1);

		cout<<need[1]<<endl;
	}
return 0;
}