HELP!My algo:find the minimum,add the edge,sort and print,the first and the third step I use the heap.I don't think these matter.
My code:

#include<iostream>
using namespace std;
const int maxn = 7500;
int heap_size = 0, now = 0;
int heap[maxn + 1];
struct edge
{
    int neighbour;
    edge *pre;
}e[maxn + 1];
edge *tail[maxn + 1];
inline void swap(int i, int j)
{
    int temp;
    temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
    return;
}
void heap_up(int i)
{
    if (i == 1) return;
    int father = i / 2;
    if (heap[i] < heap[father])
    {
        swap(i, father);
        heap_up(father);
    }
    return;
}
void heap_down(int i)
{
    int left = i * 2;
    int right = left + 1;
    int least = i;
    if (left <= heap_size && heap[left] < heap[least]) least = left;
    if (right <= heap_size && heap[right] < heap[least]) least = right;
    if (least != i)
    {
        swap(i, least);
        heap_down(least);
    }
    return;
}
inline void heap_delete(int i)
{
    swap(i, heap_size--);
    heap_down(i);
    return;
}
inline void heap_insert(int key)
{
    heap[++heap_size] = key;
    heap_up(heap_size);
    return;
}
inline void connect(int u, int v)
{
    e[++now].neighbour = v;
    e[now].pre = tail[u];
    tail[u] = e + now;
    return;
}
int main()
{
    int son[maxn + 1] = { 0 }, code[maxn];
    int n = 1, i, u, v, temp;
    do
    {
        temp = 0;
        cin >> temp;
        if (temp)
        {
            code[n++] = temp;
            son[temp]++;
        }
    } while (temp);
    for (i = 1; i <= n; i++) if (!son[i]) heap_insert(i);
    for (i = 1; i <= n; i++) tail[i] = nullptr;
    for (i = 1; i < n; i++)
    {
        v = heap[1];
        heap_delete(1);
        u = code[i];
        if (!(--son[u])) heap_insert(u);
        connect(u, v);
        connect(v, u);
    }
    edge *p;
    heap_size = 0;
    for (i = 1; i <= n; i++)
    {
        cout << i << ":";
        for (p = tail[i]; p != nullptr; p = p->pre) heap_insert(p->neighbour);
        for (; heap_size; heap_delete(1)) cout << " " << heap[1];
        cout << endl;
    }
    return 0;
}

Edited by author 06.02.2015 21:40

Edited by author 07.02.2015 08:44

 As I said before I think java programs should get higher time limit. My java program gets TLE on test #4 or #5 285ms.
In my opinion my program runs in O(nlogn). Below I gave the code that gets TLE:



import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> lst = new ArrayList<>();
        int[] sorted;
        PriorityQueue<Integer>[] g;

        int[] degree = new int[8000];
        Arrays.fill(degree, 0);

        // O(n)
        while (sc.hasNextInt()) {
            int tt = sc.nextInt() - 1;
            lst.add(tt);
            degree[tt]++;
        }

        g = new PriorityQueue[lst.size() + 1];
        sorted = new int[lst.size() + 1];
        // O(n)
        for (int i = 0; i < lst.size() + 1; i++) {
            sorted[i] = i;
            g[i] = new PriorityQueue<>();
        }

        // find initial leaves O(nlogn)
        PriorityQueue<Integer> leaves = new PriorityQueue<>();
        for (Integer y : sorted) {
            if (degree[y] == 0) {
                leaves.add(y);
            }
        }

        // O(nlogn)
        for (int x : lst) {
            degree[x]--;

            int y = leaves.poll();

            g[x].add(y);
            g[y].add(x);

            if(degree[x] == 0){
                leaves.add(x);
            }

        }

        // O(nlogn)
        for (int i = 0; i < g.length; i++) {
            System.out.print((i + 1) + ":");
            while (!g[i].isEmpty()) {
                System.out.print(" " + (g[i].poll() + 1));
            }
            System.out.println("");
        }

    }
}





Edited by author 12.12.2014 23:17

I've written the program for many times,but when I submited it,I always see "MLE" or "Wrong Answer",I've submitted it for more than 10 times!!!
Finally Accepted!!!

OK I've found that my heap is error,and I got MLE then.

Edited by author 04.03.2013 19:32


Edited by author 04.03.2013 19:32

Well, i got WA on it and then modified something and got Memory Limit Exceeded. I'm using a matrix of 7501*7501. I think i should make lists of neighbours?

- Do you know test 4 ?
- Any helpful tests ?
- If not, please pick bugs from my code. My algo: Find minimal, adjacent list, output sorted list. Tks a loooottttttt

Program Prufer_Code;
Type
        pnode = ^node;
        node = Record
         data:Longint;
         next:pnode;
End;

Var     adjList:Array[0..7500] of pnode;
        temp:pnode;
        A,C,minS:Array[0..7500] of Longint;
        n,i,j,s,p,q,m:Longint;
        fi:Text;
Procedure add(k:Longint;var x:pnode);
Var
        y,z:pnode;
Begin
        If (x=nil) then
         Begin
          new(x);
          x^.data:=k;
         End
        Else
         Begin
          new(y);
          y^.data:=k;
          y^.next:=x;
          x:=y;
         End;
End;

Begin

                n:=0;
                While not seekeof do
                 Begin
                  inc(n);
                  Read(A[n]);
                 End;

                For i:=1 to n+1 do
                 Begin
                  inc(C[i]);
                  inc(C[A[i]]);
                 End;
                dec(C[A[n+1]],2);
                p:=0;

                For i:=1 to n+1 do
                 If C[i]=1 then
                  Begin
                   inc(p);
                   minS[p]:=i;
                  End;

                For i:=1 to n do
                 Begin
                  q:=minS[1]; m:=1;
                  For j:=2 to p do
                   If minS[j]<q then
                    Begin
                     q:=minS[j];
                     m:=j;
                    End;
                  j:=q; minS[m]:=99999;


                  add(j,adjList[A[i]]);
                  add(A[i],adjList[j]);
                  dec(C[A[i]]);

                  If C[A[i]]=1 then
                   Begin
                    inc(p);
                    minS[p]:=A[i];
                   End;

                 End;

                For i:=1 to n+1 do
                 Begin
                  FillChar(C,sizeof(C),0);
                  temp:=adjList[i];
                  p:=0;
                  while temp<>nil do
                   Begin
                    inc(C[temp^.data]);
                    temp:=temp^.next;
                   End;
                  Write(i,': ');
                  For j:=1 to 7500 do
                   If C[j]=1 then Write(j,' ');
                  Writeln;
                 End;
End.

Don't forget about it ;)

I got wa on test 2

I want to know if input is : 2 2
what should I output?

sorry my English is very poor

I checked everything 100 times but still can not understand what the problem is.(i wrote on Java)

Hi,

In the question they said that the last vertex left (or last vertex of given prufer code) should be equal to N or number of nodes in the graph. But its not like that somehow, so I changed N to total numbers in prufer code + 1. Then no more WA 1.

Varun

Edited by author 08.03.2010 06:55

I use a very simple algorithm..my code is very short..
*just (for i:=1 to n do)check if the number appears in the A set of numbers after i.
*set down the father of each number.
*Just output.

(i'm sorry that my English is really bad..)

var
  con,temp,i,j:longint;
  fin:array[1..7500]of boolean;
  b,a,fa:array[1..7500]of integer;
begin
  {$IFNDEF ONLINE_JUDGE}
  assign(input,'input.in');reset(input);
  assign(output,'output.out');rewritE(output);
  {$ENDIF}
  reaD(temp);
  con:=0;
  while temp<>0 do
    begin
      inc(con);
      a[con]:=temp;
      inc(b[temp]);
      read(temp);
    end;
  for i := 1 to con do
    for j := 1 to con+1 do
      if (not fin[j])and(b[j]=0) then
        begin
          fin[j]:=true;
          fa[j]:=a[i];
          deC(b[a[i]]);
          break;
        end;
  for i := 1 to con+1 do
    begin
      write(i,':');
      for j := 1 to con+1 do
        if (fa[j]=i)or(fa[i]=j) then
          write(' ',j);
      writeln;
    end;
end.

Edited by author 13.10.2009 15:09

for example for test: 8 7 4 6 3 6 8
my program writes:
1: 8
2: 7
3: 7 6
4: 5 6
5: 4
6: 4 3 8
7: 2 3
8: 1 6

which is correct, but i got WA#2

if i sort the result:
1: 8
2: 7
3: 6 7
4: 5 6
5: 4
6: 3 4 8
7: 2 3
8: 1 6

i get TL#5

i have got AC

Edited by author 18.06.2009 02:45

Edited by author 18.06.2009 05:09

Edited by author 18.06.2009 05:42

Can you tell me an idea how to solve it in O(N) or in O(N*logN)
Thanks

Edited by author 14.03.2009 00:58

Prufer code is not N-1!!! Its should be N-2, because the last number always N. For example if I will get the numbers: 1 1 1 1 1, its impossible to build this graph. About this possible to read here:
http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence

what is it on test number 4.

Now all tests contain EOLN character after the last line of input. Use "seekeof" instead of "eof". Many authors now have WA1, TL1 or Crash1, but some others with such old verdicts got AC. Besides, some new tests were added to the problem.