Why do I get access violation? here's the code(top_sort with pointers)

type pok=^mars;
     mars=record
     redbr:integer;
     sleden:pok;
     end;
     var i,j,k,l,n,m,gl,r,pm,pm1:integer;
     brdeca,z,odg:array[1..100]of integer;
     p1,p2,p3,pom,prv:pok;
     toc:boolean;
     vl,kon,vl1:array[1..200]of integer;
     deca:array[1..150,1..150]of integer;
     t,tc,ozn:array[1..200]of boolean;
procedure stavi(y:integer);
begin
     if prv=nil then
     begin
          new(p1);
          prv:=p1;
          p1^.redbr:=y;
          p1^.sleden:=nil;
          kon[y]:=gl;
          gl:=gl+1;
     end else
     begin
          pom:=prv;
          while pom^.sleden<>nil do pom:=pom^.sleden;
          new(p2);
          pom^.sleden:=p2;
          p2^.sleden:=nil;
          p2^.redbr:=y;
          kon[y]:=gl;
          gl:=gl+1;
     end;
end;
procedure dfs(x:integer);
begin
      if tc[x]=false then
      begin
           tc[x]:=true;
           for j:=1 to brdeca[x] do vl[deca[x,j]]:=vl[deca[x,j]]+1;
           for j:=1 to brdeca[x] do if tc[deca[x,j]]=false then dfs(deca[x,j]);
      end;
end;
procedure vadi;
begin
          r:=prv^.redbr;
          for i:=1 to brdeca[prv^.redbr] do vl[deca[r,i]]:=vl[deca[r,i]]-1;
          pom:=prv;
          prv:=prv^.sleden;
          dispose(pom);
end;
begin
readln(n);
for i:=1 to n do ozn[i]:=false;
for i:=1 to n do vl[i]:=0;
for i:=1 to n do brdeca[i]:=1;
i:=1;
while i<n+1 do
begin
      read(deca[i,brdeca[i]]);
      if deca[i,brdeca[i]]<>0 then brdeca[i]:=brdeca[i]+1
      else
          begin
               brdeca[i]:=brdeca[i]-1;
               i:=i+1;
          end;
end;
gl:=0;
for i:=1 to n do
tc[i]:=false;
for i:=1 to n do dfs(i);
for i:=1 to n do vl1[i]:=vl[i];
toc:=true;
new(prv);
prv^.sleden:=nil;
for i:=1 to n do if vl[i]=0 then stavi(i);
while toc do
begin
     vadi;
     for i:=1 to brdeca[r] do if vl[deca[r,i]]=0 then stavi(deca[r,i]);
     if prv=nil then toc:=false;
end;
for i:=1 to n do z[i]:=i;
for i:=1 to n-1 do
begin
     for j:=i+1 to n do
     begin
          if kon[i]>kon[j] then
          begin
              pm:=z[i];
              pm1:=kon[i];
              z[i]:=z[j];
              kon[i]:=kon[j];
              z[j]:=pm;
              kon[j]:=pm1;
          end;
      end;
end;
for i:=1 to n-1 do write(z[i],' ');
write(z[n]);
end.

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

input:
100
0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
1 4 5 9 2 3 0
10 0
11 0
12 4 5 6 7 8 9 0
13 0
14 0
15 0
16 0
17 0
18 0
2 3 4 28 5 6 1 7 8 9 10 11 12 13 17 19 0
0
2 0
0
0
15 0
0
0
0
14 13 12 11 0
0
0
33 34 30 0
0
0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
1 4 5 9 2 3 0
10 0
11 0
12 4 5 6 7 8 9 0
13 0
14 0
15 0
16 0
17 0
18 0
2 3 4 28 5 6 1 7 8 9 10 11 12 13 17 19 0
0
2 0
0
0
15 0
0
84 0
0
14 13 12 11 0
0
0
33 34 30 0
0
0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
1 4 5 9 2 3 0
10 0
11 0
12 4 5 6 7 8 9 0
13 0
14 0
15 0
16 0
17 0
18 0
2 3 4 28 5 6 1 7 8 9 10 11 12 13 17 19 0
0
2 0
0
0
15 0
0
0
0
14 13 12 11 0
0
0
33 34 30 0
0
92 84 11 0

My program outputs:
20 53 86 19 52 85 18 51 100 84 17 50 83 16 25 49 58 82 91 15 29 48 62 81 95 14 47 80 13 46 79 12 45 78 11 44 77 10 43 76 9 42 75 8 41 74 7 40 73 6 39 72 5 38 71 4 37 70 3 22 36 55 69 88 2 35 68 1 21 23 24 26 27 28 32 65 98 30 31 33 34 54 56 57 59 60 61 63 64 66 67 87 89 90 92 93 94 96 97 99

Why is it wrong??? I think it's true, but I have WA#6!!!

Edited by author 03.01.2007 09:11

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

The test#5 is:

35
0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
1 4 5 9 2 3 0
10 0
11 0
12 4 5 6 7 8 9 0
13 0
14 0
15 0
16 0
17 0
18 0
2 3 4 28 5 6 1 7 8 9 10 11 12 13 17 19 0
0
2 0
0
0
15 0
0
0
0
14 13 12 11 0
0
0
33 34 30 0
0
0
0

what's the correct answer for test#5? Thx

what is the output of this input?
20
0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
1 4 5 9 2 3 0
10 0
11 0
12 4 5 6 7 8 9 0
13 0
14 0
15 0
16 0
17 0
18 0
2 3 4 5 6 1 7 8 9 10 11 12 13 17 19 0

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?

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.

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

{$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.

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.

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;
}