ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1022. Genealogical Tree

is my algorithm efficient??
Posted by michel mizrahi 30 Apr 2005 08:57
(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