(first...sorry for my english)
I am a beginner in this field, and this is the first problem I solve using "graph theory"
I got ac in 0.001s and 74 KB of memory
I just do a topological sort, but I have never seen an implementation of this, so I did what it seems to be the more effective way to me.

here is my code:
#include <stdio.h>
char g[101][101];

init(int n){
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            g[i][j]=0;
}

topological_sort(int n){
    int i,j,k,u,v=0;
  for(k=1;;k++)
      for(i=1;i<=n;i++){
         for(j=1;j<=n;j++){
              if(g[j][i]==1) break;
              if(j==n){
            v++;
                        if(v==n){
                            printf("%d\n",i);
                            return 0;
                        }
                        printf("%d ",i);
                        for(u=1;u<=n;u++)
                            g[i][u]=0;
                        for(u=1;u<=n;u++)
                            g[u][i]=1;
                    }
             }
      }
}

int main(){
    int n,i,j,t;
  scanf("%d",&n);
  init(n);
  for(i=1;i<=n;i++)
        for(j=1;;j++){
            scanf("%d",&t);
            if(t==0) break;
            g[i][t]=1;
        }
    topological_sort(n);
  return 0;
}
if someone can help me I would appreciatevery much
and please if someone doesn't understand my ugly code, please ask me
(I know maybe many of my codes are ugly ,slow and hard to understand )
thanks for all!
byeee


Edited by author 30.04.2005 08:59