Sorry for poor english...
I think that this code is true (but it's not topsort!):

const
  INF=2000000000;

var
  a : array [1..100] of integer;
  n,i,j,now,k,min : integer;

begin
  read(n);
  for i:=1 to n do
    a[i]:=i;
  for i:=1 to n do begin
    read(k);
    min:=INF;
    while k<>0 do begin
      for j:=1 to n do
        if (a[j]=k) and (min>j) then
          min:=j;
      read(k);
    end;
    if min<>INF then begin
      for j:=1 to n do
        if a[j]=i then
          now:=j;
      if now>min then begin
        for j:=now downto min+1 do
          a[j]:=a[j-1];
        a[min]:=i;
      end;
    end;
  end;
  write(a[1]);
  for i:=2 to n do
    write(' ',a[i]);
end.

May you give me some bad for my algorithm tests? Thanks for your attention.

Edited by author 04.03.2007 00:54

Edited by author 04.03.2007 00:55

i used topologic sort, described here -> http://en.wikipedia.org/wiki/Topological_sorting, but got wa on second test. (i believe i implemented algo correctly.)
maybe there is something important, that they did not mention?

Edited by author 11.12.2006 17:46

Somebody has solved this task? And how it to solve?
I can not any more.
When I check, all normal, but the system shows, that on the fourth test a error.

input:
5
0
4 5 1 0
1 0
5 3 0
3 0
output:
2 4 5 3 1
but where is 2 in input?

Here is my program, I dont why I get WA?
My algorithm is correct!

var
  a:array[1..100,1..100] of integer;
  b:array[1..100] of integer;
  i,j,nn,n,k:integer;

procedure readdata;
begin
  readln(n);
  for i:=1 to n do
  begin
    j:=0;
    repeat
      inc(j);
      read(a[i,j]);
    until a[i,j]=0;
    a[i,j]:=-1;
  end;
end;

procedure writedata;
begin
  for i:=1 to n do
  write(b[i],' ');
end;

function check(i,nn:integer):boolean;
var
  j:integer;
begin
  j:=1; check:=false;
  if a[nn,j]<>-1 then
  repeat
    if a[nn,j]=i then
    begin
      check:=true;
      exit;
    end;
    inc(j);
  until a[nn,j]=-1;
end;

procedure push(k,nn:integer);
var
  x,m,j,i:integer;
begin
  j:=1;
  while (b[j]<>k) do inc(j);
  m:=j;

{  x:=b[k];}
  for j:=nn downto k do
  if (j-1<1) then break else
  b[j]:=b[j-1];
{  b[nn]:=x;}

{  j:=nn;
  while (b[j]<>m) do
  begin
    b[j]:=b[j-1];
    dec(j);
  end;}

  b[m]:=nn;
end;

begin
  readdata;
  repeat
    inc(nn);
    b[nn]:=nn;
    k:=0;
    for i:=nn downto 1 do
    if (i<>nn) and (check(i,nn)) then k:=i;
    if k<>0 then push(k,nn);
  until nn=n;
  writedata;
end.

Sample Input

5
0
4 5 1 0
1 0
5 3 0
3 0
Sample Output

2 4 5 3 1


WHERE DIN THE "2" come from????

 can someone give me the test case #5?

 i got wa on that case.
 i'm using method of giving points to each person, so that every child has more points than his father. i'm doing that with bfs:

if points[child] <= points[parent]
  points[child] = points[parent] + 1;
bfs (child);

 i think method is right.

#include <iostream>
using namespace std;
//-------------------------------------------------------------------
class TStack
{
public:
    TStack* Insert(int Value);
    TStack* Add(int x);
    TStack * Next;
    int Value;
    TStack();
};
bool Find(int Value, TStack *ptr);
void deleteStack(TStack *ptr);
//-------------------------------------------------------------------
int main()
{
    TStack * Head = new TStack();
    TStack * ptr;
    ptr = Head;
    int N;
    cin >> N;
    for(int i=0;i<N;i++)
    {
        TStack * HeadArray = new TStack();
        TStack * ptrArray = HeadArray;
        int Ai;
        cin >> Ai;
        while(Ai != 0)
        {
            ptrArray = ptrArray->Add(Ai);
            cin >> Ai;
        }
        ptr = Head;
        bool flag = true;
        while(flag)
        {
            if(i == 0)
            {
                ptr->Add(i+1);
                flag = false;
            }
            else
            {
                bool change = true;
                while(ptr->Next != NULL && change)
                {
                    ptrArray = HeadArray;
                    if(Find(ptr->Next->Value,ptrArray))
                    {
                        ptr->Insert(i+1);
                        change = false;
                    }
                    else
                    {
                        ptr = ptr->Next;
                    }
                }
                if(change)
                {
                    ptr->Add(i+1);
                }
                flag = false;
            }
        }
        deleteStack(HeadArray);
    }
    ptr = Head->Next;
    while(ptr != NULL)
    {
       cout << ptr->Value << " ";
       ptr = ptr->Next;
    }
    deleteStack(Head);
    cin >> N;
    return 0;
};
//-------------------------------------------------------------------
bool Find(int Value, TStack *ptr)
{
    bool result = false;
    while(ptr != NULL && !result)
    {
        if(ptr->Value == Value) result = true;
        else
        {
            ptr = ptr->Next;
        }
    }
    return result;
}
//-------------------------------------------------------------------
TStack::TStack()
{
    Next = NULL;
    Value = 0;
}
//-------------------------------------------------------------------
TStack* TStack::Add(int x)
{
    TStack * ptrValue = new TStack();
    ptrValue->Value = x;
    Next = ptrValue;
    return ptrValue;
}
//-------------------------------------------------------------------
TStack* TStack::Insert(int Value)
{
    TStack *ptrValue = new TStack();
    ptrValue->Value = Value;
    ptrValue->Next = Next;
    Next = ptrValue;
    return ptrValue;
}
//-------------------------------------------------------------------
void deleteStack(TStack *ptr)
{
     while(ptr != NULL)
     {
        TStack *ptrBuff = ptr;
        ptr = ptr->Next;
        delete ptrBuff;
     }
     return;
}

If someone have the test#6, please send to kilobyte@nm.ru.

(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

see the subject !

{$APPTYPE CONSOLE}

var
  n,i,j,p:integer;
  c:array[1..2,1..100] of integer;
  a:array[1..100,0..100] of integer;
procedure sort(l,r: integer);
var
  i,j,x,y: integer;
begin
  i:=l; j:=r; x:=c[1,(l+r) DIV 2];
  repeat

    while X<c[1,i] do i:=i+1;
    while x>c[1,j] do j:=j-1;
    if i<=j then
    begin
      y:=c[1,i]; c[1,i]:=c[1,j]; c[1,j]:=y;
      y:=c[2,i]; c[2,i]:=c[2,j]; c[2,j]:=y;
      i:=i+1; j:=j-1;
    end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;



function count(nom:integer):integer;
 var i:integer;
 var kol:integer;
begin
   if c[1,nom]<> 0 then  count:=c[1,nom] else
   begin
      kol:=0;
      inc(kol);
      for i:=1 to a[nom,0] do inc(kol,count(a[nom,i]));
      c[1,nom]:=kol;
      count:=kol;
   end;
end;
begin
   assign(Input,'input.txt'); assign(Output,'output.txt');
{   reset(Input);              rewrite(Output);}
   readln(n);
   for i:=1 to n do
   begin
     j:=0;
     while not eoln do
     begin
        inc(j);
        read(a[i,j]);
     end;
     a[i,0]:=j-1;
     readln;
   end;
   for i:=1 to n do
   begin
      c[1,i]:=count(i);
      c[2,i]:=i;
   end;
   sort(1,n);
   for i:=1 to n do write(c[2,i],' ');
   writeln;

   {close(Input);               close(Output);}
end.

Program ural1022;
Const
  maxn=110;
Var
  list,num:array[0..maxn] of longint;
  map:array[0..maxn,0..maxn] of byte;
  i,m,n,ptr,j,c:longint;




Procedure Pre;
Begin
  fillchar(num,sizeof(num),0);
  for i:=1 to n do
    for j:=1 to n do
      if map[j,i]=1 then inc(num[ i ]);
  ptr:=0;
  for i:=1 to n do
    if num[ i ]=0 then
      begin
        inc(ptr);
        list[ptr]:=i
      end
End;



Procedure work;
Begin
  pre;
  while ptr<n do
    begin
      m:=list[ptr];
      for i:=1 to n do
        if map[m,i]=1 then
          begin
            dec(num[ i ]);
            if num[ i ]=0 then
              begin
                inc(ptr);
                list[ptr]:=i
              end
           end
    end
End;



Procedure out;
Begin
  for i:=1 to ptr do
    if i<>ptr then write(list[ i ],' ') else writeln(list[ i ])
End;



Begin
{  assign(input,'input.txt');
  reset(input);}
  readln(n);
  fillchar(map,sizeof(map),0);
  for i:=1 to n do
    begin
      read(c);
      while c<>0 do
        begin
          map[i,c]:=1;
          read(c)
        end;
      readln
    end;
  work;
  out
End.

In the sample input:
It is said that 3 is 5's child,and 3 is 4's child,and 5 is 4's child.
It is an illegal relationship in the realistic, isn't it?
It seems that 5 is 4's child,and 5 and 4 are 3's parents!

Hello guys,

This problem doesn't seem to be so complicated, and my code works
find in all the cases that I have tried, can anyone give me some
extreme cases or take a look at the source?

Thanks in advanced

Oscar

//------------------------------------------------------------


#include <stdio.h>
#include <string.h>

short tree[101][101], list[101], n, i, j,l;

void inicializa(void);
void lee_valores(void);
void hazlo(int v);

void main(void)
    {
    scanf("%d", &n);
    inicializa();
    lee_valores();
    for (i=1; i<n+1; i++){
        if (!visitado[i]) hazlo(i);
        }
    }

void hazlo(int v)
     {
     visitado[v]=1;
     for (j=n; j>0; j--)
     if ((tree[j][v]) && (!visitado[j]))
        hazlo(j);
     printf("%d ", v);
     }

void inicializa(void)
     {
     memset(tree, 0, sizeof(tree));
     memset(list, 0, sizeof(list));
     memset(visitado, 0, sizeof(visitado));
     }

void lee_valores(void)
     {
     int temp;
     for(i=1; i<n+1; i++){
        for(j=1; j<n+1; j++){
        scanf("%d", &temp);
        if (temp == 0) break;
        tree[i][temp] = 1;
        }
        }
     }

#include <iostream.h>

const int max=100;
int N, G[max][max], color[max], sorted[max], last_sorted;

///////////////////////////////////////

void DFS_VISIT(int i)
{
    color[i]=1;

    for(int j=1;G[i][j]!=0;j++) {
        if (color[G[i][j]]==0)
            DFS_VISIT(G[i][j]);
    }

    color[i]=2;
    last_sorted++;
    sorted[last_sorted]=i;
}

void DFS()
{
    for(int i=1;i<=N;i++) {
        color[i]=0;
    }
    for(i=1;i<=N;i++)
        if (color[i]==0)
            DFS_VISIT(i);
}

//////////////////////////////////////

int main() {
    cin >> N;

    for(int i=1;i<=N;i++) {
        int x=1;
        for(int j=1;x!=0;j++) {
            cin >> x;
            G[i][j]=x;
        }
    }

    last_sorted=0;
    DFS();

    for(i=last_sorted;i>0;i--)
        cout << sorted[i] << ' ';
    return 0;
}

just using top-sort

program ex;
const maxn=100;
var   b:array[1..maxn] of integer;
      g:array[1..maxn,1..maxn] of integer;
      i,j,k,n:integer;

begin
    fillchar(b,sizeof(b),0);
    fillchar(g,sizeof(g),0);
    readln(n);
    for i:=1 to n do begin
        read(j);
        while (j<>0) do begin
            inc(b[j]);
            g[j,i]:=1;
            read(j);
        end;
    end;

    for i:=1 to n do begin
        j:=1;
        while (b[j]<>0) do     inc(j);
        write(j,' ');
        b[j]:=maxint;
        for k:=1 to n do
            if (g[k,j]=1) then dec(b[k]);
    end;
    writeln;
end.

how much time dose these problem take?

how much time dose these problem take?