Poj Solution 1694

http://poj.org/problem?id=1694

#include<iostream>
#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;
}




											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *