i just can't understand what does this problem want from me.
1. what is the number of a vertex? (is it by any chance the cost of the way connecting its two extremes?)
2. what is the rule by which different lines in the graph are assigned costs?
in the example:
   1
  /  4   6
     |
     2
    /    3   5

what are the costs of
(1,4)
(1,6)
(6,2)
(2,3)
(2,5)
?

thank you
        foxx@email.ro

the problem is
u are given a prufer code
and u must output what graph that give this code

ie in the sample input

4-1-6-2-5
         |
         3

to construct the prufer code is look all leaf and find the smallest
then next code=the number of vertex that connect it

we find that
leaf = 4 3 5 ( 3 is the smallest then write 2 down )

then the graph will be
4-1-6-2-5

code = 2

leaf = 4 5 ( 4 is the smallest the write 1 down )

then the graph will be
1-6-2-5

code = 2 1

leaf= 1 5 ( 1 is the smallest then write 6 down )
graph
6-2-5

code= 2 1 6

and so on..

> the problem is
> u are given a prufer code
> and u must output what graph that give this code
>
> ie in the sample input
>
> 4-1-6-2-5
>          |
>          3
>
> to construct the prufer code is look all leaf and find the smallest
> then next code=the number of vertex that connect it
>
> we find that
> leaf = 4 3 5 ( 3 is the smallest then write 2 down )
>
> then the graph will be
> 4-1-6-2-5
>
> code = 2
>
> leaf = 4 5 ( 4 is the smallest the write 1 down )
>
> then the graph will be
> 1-6-2-5
>
> code = 2 1
>
> leaf= 1 5 ( 1 is the smallest then write 6 down )
> graph
> 6-2-5
>
> code= 2 1 6
>
> and so on..
>

wow that's sound great : )

but mine's still got TL - -'
i don't know why(i already use heap)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 30000
#define CON 2000000000
struct node { long info; struct node *next; };
typedef struct node *nodeptr;
long arr[MAX*2],num[MAX],deg[MAX],n;
long nheap;
FILE *fp,*fx;
nodeptr res[MAX];
void input(void)
{
 long tmp;
 n=1;
 while(fscanf(fp,"%ld",&tmp)!=EOF)
   {
    num[n++]=tmp;
    deg[tmp]++;
   }
}
nodeptr getnode(long i,nodeptr next)
{
 nodeptr p;
  p=(nodeptr)malloc(sizeof(struct node));
  p->next=next; p->info=i;
 return p;
}
void add(long a,long b)
{
 nodeptr p,q;
 if( res[a]==NULL||b<res[a]->info)
  { res[a]=getnode(b,res[a]); return; }
 for(p=q=res[a];p!=NULL&&b>p->info;p=p->next) q=p;
 p=getnode(b,p); q->next=p;
}
void del(void)
{
 long pos,tmp,nextpos;
 arr[1]=CON;
 for(pos=1,tmp=arr[1];;)
  {
   if(arr[pos*2]<arr[pos*2+1]) nextpos=pos*2;
   else nextpos=pos*2+1;
   if(tmp>arr[nextpos])
     { arr[pos]=arr[nextpos]; pos=nextpos; }
   else break;
  }
 arr[pos]=tmp;
}
void insert(long a)
{
 long pos,k;
 for(k=10000;;k--) if(arr[k]==CON) break;
 nheap++;
 arr[k]=a;
 for(pos=k;pos>1;pos/=2)
  {
   if(a<arr[pos/2]) arr[pos]=arr[pos/2];
   else break;
  }
 arr[pos]=a;
}
void process(void)
{
 long i;
 for(i=0;i<MAX*2;i++) arr[i]=CON;
 for(i=1,nheap=0;i<=n;i++) if(!deg[i]) arr[++nheap]=i;
 for(i=1;i<n;i++)
   {
     add(arr[1],num[i]); add(num[i],arr[1]);
     del();
     deg[num[i]]--; if(!deg[num[i]]) insert(num[i]);
   }
}
void output(void)
{
 long i;
 nodeptr p;
 for(i=1;i<=n;i++)
  {
   fprintf(fx,"%ld:",i);
   for(p=res[i];p!=NULL;p=p->next) fprintf(fx," %ld",p->info);
   fprintf(fx,"\n");
  }
}
int main()
{
  fp=stdin; fx=stdout;
// fp=fopen("1069.in","r"); fx=fopen("1069.out","w");
  input();
  process();
  output();
// fclose(fp); fclose(fx);
 return 0;
}

i can't see why you dudes use heaps...
and i am too dumb at this time to understand your src
the algo goes like:
----------------------------------------------------
1: read i and inc number of apparitions of the node i;
2: last = 1;
3: for i = 1 .. n
4:   while apparitions of node[last] > 0 inc last;
   // now you have found (i, last) a valid vertex in the source tree
5:   memorize vertices (i, last) and (last, i);
6:   dec apparitions[i];
7:   dec apparitions[last];   // it gets -1 which is different of 0 :)
8:   if apparitions[i] = 0 and i < last
9:       last = i;
----------------------------------------------------

in 5 i simply push the 2 pairs in one stack and in final i take from each of n stacks the values and brutely qsort() on em.
got .3secs @ 600 kBs
foxx@email.ro

I see. Such as Qsort is O(n^2) in the worst case, you algo is also fast for average cases...